시간복잡도 (big - O,big - Omega,big - Theta) 표기법

입력 크기 n에 따른 실행시간 증가율을 나타낼 수 있다.

 

• Big O 표기법
• Omega 표기법
• Theta 표기법

 

Big O:

 - 상한선을 표현하는 방법이므로, 이 알고리즘은 O(n)보다는 작을 것임

 - n>k일 때 f(n) <= C *g(n) 을 만족하는 k, C가 존재하면 f(n)=O(g(n))이다.

 

Omega:

 - 하한선을 표현하는 방법이므로, 이 알고리즘은 Ω(n)보다는 클 것임

- n>k일 때 f(n) >= C *g(n) 을 만족하는 k, C가 존재하면 f(n) = Ω(g(n))이다.

- (Big O의 반대라고 보면 된다)

 

big Theta:

 - f(n)=O(g(n)) 이고 f(n) = Ω(g(n))일 때,  f(n)=Θ(g(n))이다.

 

 

 

예제 프로그램들의 근사 표현

이진탐색: T(n) = T(n/2)+1, T(1) = 1 ==> O(log2 n)

순열출력: T(0,n) = (n+1)*T(1,n), T(n,n) = n+1 ==> O(n^2 * n!)

 

 

문제풀이는 대충적었으니까 참고하지마시오