Time Complexity Analysis

Time Complexity Analysis : 시간 복잡도

 

▶ 시간 복잡도 표기법

 

① Big O Notation	② Big Ω Notation	③ Big θ Notation
함수의 상한 나타냄	함수의 하한 나타냄	함수의 상한과 하한 나타냄
모든 n >= n0 에 대하여, |f(n)| <= c |g(n)| 을 만족하는 상수 c와 n0이 존재하면, f(n) = O(g(n)) 이다.	모든 n >= n0 에 대하여, |f(n)| >= c |g(n)| 을 만족하는 상수 c와 n0이 존재하면, f(n) = Ω(g(n)) 이다.	모든 n >= n0 에 대하여,  c1 |g(n)| <= f(n) <= c2 |g(n)| 을 만족하는 상수 c1, c2, n0이 존재하면, f(n) = θ(g(n)) 이다.

 

- 일반적으로는 최악의 경우를 고려한 해결책을 찾으므로, 주로 Big O Notation을 이용한다.