Big Oh 표기법 (최고차항 기준)
Big Omega 표기법도 최고차항 기준으로 알고리즘의 하한을 나타냅니다.
빅세타 표기법은 알고리즘의 상한과 하한을 모두 고려하는 표기법입니다. 최고차항과 최저차항이 같은 경우, 빅세타는 빅오와 빅오메가의 중간값을 가집니다.
빅오메가와 빅오가 같을 경우 빅세타도 같음
널 레퍼런스 수 = 노드수(차수-1) + 1
노드 100개 차수 10이면 → 900+1 = 901개의 널 레퍼런스를 가짐
알고리즘의성능은수행시간을나타내는시간복잡도(Time Complexity)와 알고리즘이수행되는동안사용되는메모리공간의 크기를나타내는공간복잡도(Space Complexity)에기반하여분석한다.
평균경우분석은입력의확률분포를가정하여분석하는데,
최선경우분석은거의 사용되지않으나, 최적(Optimal) 알고리즘®을찾는데활용되기도한다.
상각분석은일련 의연산을수행하여총 연산횟수를합하고이를연산횟수로나누어수행 시간을분석하 는방법
빅오 = 상한
빅오메가 = 하한