점근적 표기법

 

 

쉽게 배우는 알고리즘(문병로) 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)$)