스택프레임, 빅오

by

스태킹 프레임

  • 함수가 호출되면 스택 프레임이라는 영역이 생성됩니다.
  • 함수 실행에 필요한 지역 변수는 이 스택 프레임에 할당됩니다.
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 함수를 호출하면 내부적으로 “스택 프레임”이라는 내부 범위와 로컬 변수 C가 생성되어 add_two 함수 내부에 매개 변수 a와 b를 저장하고 결과 값을 저장합니다. 이 방에서

스택 프레임은 메모리에 생성되며 생성할 수 있는 크기에는 제한이 있습니다. 이때 발생하는 오류는 재귀 깊이 오류입니다. 이를 방지하려면 함수 호출을 차단할 기본 사례가 필요합니다. 기본 사례는 전달된 매개 변수 값이 특정 값에 도달할 때 함수가 호출되지 않도록 합니다.

데이터 구조 성능 사례: Big O

  1. 정당성
    • 알고리즘의 효율성을 나타냅니다. 점근적 표기법
    • 알고리즘의 효율성이란 데이터의 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈과 같은 기본 연산이 얼마나 자주 수행되는지를 의미합니다.
    • Big-O 표기법은 일반적으로 알고리즘의 시간적 복잡성과 공간적 복잡성을 표현하는 데 사용됩니다.
  2. 유형
    1. 오(1)
      • 알고리즘은 일정한 시간과 데이터 구조에 저장된 데이터 수와 관계없이 고정된 작업 수 내에서 완료됩니다.
      • 가장 좋은 예는 동적 배열의 인덱싱입니다.
    2. O(로그 n)
      • 이를 로그 시간이라고 합니다. 대수 플롯을 고려하면 y=x로 플롯된 선형 시간보다 성능이 훨씬 우수하다고 말할 수 있습니다.
      • 대표적인 예로서, 이진 탐색 트리 계열(이진 탐색 트리, 균형 이진 트리, B-트리)에 속하는 데이터 구조의 모든 삽입, 검색 및 삭제는 로그 시간입니다.
    3. 에)
      • 선형 시간입니다. 데이터 양이 증가함에 따라 작업 수는 선형적으로 증가합니다. O(n)에서 실제 함수를 생성할 수 있다면 그 성능은 충분히 만족스럽다고 할 수 있습니다.
      • 연결 목록 검색 및 동적 배열에서 배열 끝에 요소를 추가하는 작업을 제외한 삽입 및 삭제 작업은 선형 시간입니다.
    4. O(로그 n)
      • 선형 로그 시간입니다. 그래프를 그리면 O(n)에 비하면 성능이 떨어지지만 O(n²)에 비하면 성능이 매우 좋다.
      • 비교 정렬 중에서 가장 성능이 좋은 것으로 알려진 빠른 정렬과 병합 정렬은 모두 O(nlog n)이다.
    5. O(n²), O(n³)
      • 데이터 양이 증가함에 따라 작업 수가 가파르게 증가합니다.
      • 이것은 이중 발사와 삼중 발사를 실행한 성과입니다.
    6. 오(2ⁿ)
      • 기하급수적 시간이다. O(n²), O(n³)보다 훨씬 나쁩니다. 많은 양의 데이터에 대해 이 성능이 있는 경우 함수 실행이 너무 느릴 수 있습니다.
  3. 빅오의 함정
    • Big O는 작업 수를 기준으로 한 상대적인 기준이므로 하드웨어 또는 기타 외부 요인을 전혀 고려하지 않습니다.
    • 예를 들어, 메인 메모리에서 값을 검색하거나 저장하려면 20~100클록 주기가 필요한 반면, 디스크에서 값을 검색하거나 저장하려면 거의 5000만~500만 클럭 주기가 필요합니다.

'추천 관련글,