시간복잡도

1. Big - O 표기법

• f(n) = 2n^2 - 8n + 3 => O(n^2)
• 단순화된 함수 n^2이 임의의상수 c를 곱한 cn^2이 n이 증가함에 따라 f(n)의 상한이 된다. (단, c > 0)

• f(n) = O(g(n))
• 복잡도의 점근적 상한을 의미
• n이 증가함에 따라 O(g(n))이 점근적 상한이라는 것을 보여준다.
• cg(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 크다.

 

2. Big - Ω 표기법

• f(n) = 2n^2 - 8n + 3 => Ω(n^2)
• f(n) = Ω(n^2) 은 'n이 증가함에 따라 2n^2 - 8n + 3이 cn^2보다 작을 수 없다'라는 의미
• f(n) = Ω(g(n))
• 복잡도의 점근적 하한을 의미
• n이 증가함에 따라 Ω(g(n))이 점근적 하한이라는 것을 보여준다.
• cg(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 작다.

 

3. Theta 표기법

• O-표기와 Ω-표기가 같은 경우에 사용
• f(n) = 2n^2 - 8n + 3의 Θ-표기는 Θ(n^2)
• 'f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다'라는 의미

• f(n) = Θ(g(n))
• n0보다 큰 모든 n에 대해서 Θ-표기가 상한과 하한을 동시에 만족한다는 것을 보여준다.