[알고리즘] 점근적 표기법

O 표기법

Big O 표기법이라고 읽는다.

알고리즘의 Time Complexity를 분석하는 데 가장 많이 쓰이는 표기법이다.

O(g(n)) = { f(n) | 충분히 큰 n에 관해서 f(n)<= c*g(n)인 양의 "상수" c가 존재한다 }

를 의미한다.

즉 n+100= O(n)이라고 하면

n에 2를 곱함으로써 충분히 큰 n에 관해서는 n+100 < 2n이 성립할 수 있다는 말이다.

그런데 정의에 의하면 f(n)<= c*g(n)만 성립하면 어떤 f, g가 와도 상관이 없으므로

극단적으로는 n+1= O(n^10)도 가능하다.

그래서 O표기법은 엄밀한 상한을 의미할 수도 있지만 위와 같이 여유있거나 극단적인 상한이 될 수도 있다.

그러나 일반적인 알고리즘의 시간복잡도를 분석하는데 사용하는 만큼 엄밀한 의미로 많이 쓰인다.

(ex- 복잡도가 2n*log n인 알고리즘에 대해 O(n^2), O(n^44) 등 많은 O표기법 후보가 존재하지만 주로 O(n*log n)으로 표기한다)

Big Omega 표기법

Big O 표기법과는 약간 반대의 성질을 띈다.

Omega(g(n)) = { f(n) | 충분히 큰 n에 관해서 f(n)>= c*g(n)인 양의 "상수" c가 존재한다 }

를 의미한다.

즉 알고리즘의 하한을 의미한다.

O표기법과 마찬가지로 이는 극단적으로도 사용이 가능하다.

2*n^2에 관해 Omega(n) 처럼 극단적인 하한으로 표기할 수도 있다.

Big Theta 표기법

Big O와 Big Omega로 표현된 점근적 증가량이 같게 표기된다면 Big Theta 표기법을 사용할 수 있다.

Big Theta= { Big O and Big Omega} 로 정의된다.

즉 Big O와 Big Omega처럼 극단적 예를 포함하지 않고 엄밀한 의미의 점근적 증가량을 나타낸다.

n^2+ 3*n+ 1023에 관해 Big Theta (n^2)처럼 표기한다.