스택프레임, 빅오

스택 프레임

• 함수가 호출되면 스택 프레임이라는 공간이 생긴다.
• 이 스택 프레임에는 함수 실행에 필요한 지역변수들이 할당된다.

def add_two(a,b):
	c = a + b # 4
	return c

a = 10 # 1
b = 20 # 2
result = add_two(a, b) # 3
print(result)

#1과 #2는 프로그램이 시작되면서부터 끝날 때까지 메모리에 유지되는 전역변수이다. #3에서 a와 b를 인수로 전달하고 add_two 함수를 호출하면 내부적으로 ‘스택 프레임’이라는 내부 공간이 생기고, 그 공간에 add_two 함수 내부에 있는 매개변수 a, b와 그 결괏값을 담을 지역 변수 C가 저장된다.

스택 프레임은 메모리에 생성되는데 생성될 수 있는 크기에 한계가 있다. 이때 발생하는 에러가 Recursion Depth 에러이다. 이를 방지하려면 함수 호출을 막아 줄 기저 사례가 필요하다. 기저 사례는 전달받은 매개변수 값이 특정 값에 도달하면 함수가 호출되는 것을 막아준다.

 

자료 구조 성능이야기: 빅오

1. 정의
   • 알고리즘의 효율성을 표기해 주는 점근 표기법
   • 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.
   • 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다
2. 종류
   1. O(1)
      • 상수 시간, 자료 구조에 저장된 데이터 개수와 상관 없이 정해진 횟수의 연산 안에 알고리즘이 마무리된다.
      • 가장 좋은 예로 동적 배열의 인덱싱이 있다.
   2. O(log n)
      • 로그 시간이라고 한다. 로그의 그래프를 생각해 보면 이는 y=x로 그려지는 선형시간에 비해 성능이 월등히 좋다고 할 수 있다.
      • 대표적인 예로 이진 탐색 트리 계열에 속하는 자료 구조(이진 탐색 트리, 균형 이진트리, B 트리)의 삽입과 탐색, 삭제 모두 로그 시간이다.
   3. O(n)
      • 선형 시간이다. 데이터 개수가 늘어날수록 선형으로 연산 횟수가 늘어난다. 실제 함수를 만드는 데 O(n)으로 만들 수 있다면 충분히 만족할 만한 성능이라고 할 수 있다.
      • 연결 리스트의 탐색 연산과 동적 배열에서 배열 마지막에 원소를 추가하는 연산을 제외한 삽입·삭제 연산이 선형 시간이다.
   4. O(nlog n)
      • 선형 로그 시간이다. 그래프를 그려 보면 O(n)과 비교했을 때는 성능이 나쁘지만 O(n²)과 비교하면 성능이 매우 좋다.
      • 비교 정렬 중에서 가장 성능이 좋다고 알려진 퀵 정렬과 병합 정렬 등이 모두 O(nlog n)이다.
   5. O(n²), O(n³)
      • 데이터의 개수가 늘어날수록 연산 횟수가 가파르게 상승한다.
      • 이중 포문과 삼중 포문을 실행할 때 성능이다.
   6. O(2ⁿ)
      • 지수 시간이다. O(n²), O(n³) 보다 훨씬 성능이 좋지 않다. 데이터 개수가 많을 때 이런 성능을 가진다면 함수 실행이 너무 늦어질 수 있다.
3. 빅오의 함정
   • 빅오는 연산 횟수를 기반으로 한 상대적인 기준이기 때문에 하드웨어나 다른 외부적인 요소를 전혀 고려하지 않는다.
   • 예를 들면 메인 메모리에서 값을 가져오거나 저장하는 데는 20~100 클럭이 필요한 반면, 하드 디스크에서 값을 가져오거나 저장하는 데는 50~500만 가까운 클럭이 필요하다