-
쉽게 배우는 알고리즘(문병로) p.39~
뇌를 자극하는 알고리즘(박상현) p.471~
점근적 표기법(Asymptotic Notation) : 알고리즘의 수행 시간을 대략적으로 나타내는 방법.
→ 최고차항만 남긴 후 계수 제거
Θ($f(n)$) : 최고차항의 차수가 $f(n)$과 일치하는 함수의 집합
- $3n^2+2n$ = Θ($n^2$)
- $n^2+\sqrt{n}$ = Θ($n^2$)
- 버블 정렬 : Θ($n^2$), 병합 정렬 : Θ($n$log$n$)
O($f(n)$) : 최고차항의 차수가 $f(n)$과 일치하거나 더 작은 함수의 집합. 함수의 점근적 상한 → 어떤 최악의 상황에서도 이 성능 보장
- $3n^2+2n$ = O($n^2$)
- $5n$ = O($n^2$) → $5n$의 증가율이 $n^2$의 증가율보다 작아서
- (빠름) O($1$) - O(log$_{2}n$) - O($n$) - O($n$log$n$) - O($n^2$) - O($n^3$) - O($2^n$) (느림)
Ω($f(n)$) : 최고차항의 차수가 $f(n)$과 일치하거나 더 큰 함수의 집합. 함수의 점근적 하한 → 아무리 좋은 케이스라도 이 성능 이상 낼 수 없음
- $3n^2+2n$ = Ω($n^2$)
- $5n^3$ = Ω($n^2$) → $5n^3$의 증가율이 $n^2$의 증가율보다 커서
⇒ Θ($f(n)$) = O($g(n)$) $\bigcap$ Ω($g(n)$)