1. \(O\) (big-O) 표기법

1) 정의

어떤 알고리즘의 시간복잡도를 입력크기 \(n\) 에 관한 다항식 \( f(n) \) 으로 나타냈을 때,

어떤 양수 \(n_0\) 보다 큰 모든 \(n\) 에 대하여 \(f(n) \le k \cdot g(n) \) 을 만족하는 양수 \(k\) 와 \(n_0\) 가 존재한다면 \(f(n) = O( g(n) )\) 으로 정의된다.

2) 이해

- 알고리즘의 시간복잡도를 구체적으로 계산해 보면 그 식이 복잡하게 나오는 경우가 많다. 예를 들어, 어떤 알고리즘의 시간복잡도를 구체적으로 계산해 보았더니 \(3n^2 - 2n\) 이라는 다항식이 나왔다고 하자. 이를 두고 ‘이 알고리즘의 시간복잡도가 \(3n^2 - 2n\) 이다.’ 라고 이야기하는 것은 정확할 수는 있으나 매번 이와 같이 설명하는 것은 상당히 번거로운 일이다.

- big-O 표기법을 이용해 훨씬 간단하게 표현할 수 있다. 이 경우 정의에 따를 때 부등식의 \(g(n)\)에  \( n^2 \)을 대입해도 부등식을 성립시키는 양수 \(k\) 와 \(n_0\) 을 찾을 수 있으므로, 이 알고리즘의 시간복잡도를  \(O( n^2 )\)이라 쓸 수 있다.

- 이처럼 big-O 표기법을 이용하면 특정 알고리즘의 시간복잡도의 부등식의 상한( \(g(n)\) ) 부분을 간소하게 설명할 수 있다. big-O 표기법에서 쓰이는 다항식 \(g(n)\)이 부등식의 상한이므로, \(O(g(n))\)을 ‘점근적 상한‘이라 부르기도 한다.

- big-O 표기법은 시간복잡도식의 상한에 대한 부등식을 정의로 포함하므로, big-O 표기법을 이용하면 알고리즘의 최악의 경우의 시간복잡도를 비교적 명확히 표현할 수 있다.

- big-O 표기법의 정의에 의할 때 다항식 \(g(n)\)은 반드시 \(f(n)\)과 최고차항의 차수가 동일해야 하는 것은 아니며 최고차항의 차수가 \(f(n)\)보다 더 크더라도 big-O 표기법의 정의에 부합한다. 즉 엄밀히 말해 \(f(n) = O( g(n) )\)을 만족하는 \(g(n)\)의 개수는 무수히 많다. \(O(g(n))\)의 \(g(n)\)이 되도록 알고리즘의 시간복잡도의 상한에 가깝게 낮은 찾수가 되도록 쓰는 것은, 알고리즘의 시간복잡도에 관해 우리가 가장 궁금해하는 부분인 ‘알고리즘의 시간복잡도의 상한‘이라는 주제에 충실하기 위한 관용적 사용인 것이다.

2. \(\Omega\) (big-omega) 표기법

1) 정의

어떤 알고리즘의 시간복잡도를 입력크기 \(n\) 에 관한 다항식 \(f(n)\) 으로 나타냈을 때,

어떤 양수 \(n_0\) 보다 큰 모든 \(n\) 에 대하여 \(k \cdot g(n) \le f(n) \) 을 만족하는 양수 \(k\) 와 \(n_0\) 가 존재한다면 \(f(n) = \Omega( g(n) )\) 으로 정의된다.

2) 이해

- \(\Omega\) 표기법은 반대로 시간복잡도의 하한을 나타내기 위한 표기법으로, ‘점근적 하한‘이라고도 한다. ‘알고리즘이 아무리 빨라도 이 시간 이상은 걸린다’라는 정보를 아는 데 도움이 된다.

3. \(\Theta\) (big-theta) 표기법

1) 정의

어떤 알고리즘의 시간복잡도를 입력크기 \(n\) 에 관한 다항식 \( f(n) \) 으로 나타냈을 때,

어떤 양수 \(n_0\) 보다 큰 모든 \( n \) 에 대하여 \( k_1 \cdot g(n) \le f(n) \le k_2 \cdot g(n) \) 을 만족하는 양수 \(k_1\), \(k_2\) 와 \(n_0\) 가 존재한다면 \( f(n) = \Theta( g(n) ) \) 으로 정의된다.

2) 이해

- \(\Theta\) 표기법은 big-O와 \(\Omega\) 표기법의 교집합으로, 시간복잡도의 최고차항의 차수를 분명하게 표현하는 경우에 사용된다.

- 1보다 큰 모든 실수 \(a\), \(b\)에 대해 \(log_a n = \Theta (log_b n)\) 이다. 즉, 시간복잡도 함수의 로그 차수 항의 경우 그 밑이 서로 다르더라도 각각의 시간복잡도는 (\(\Theta\) 표기법 상으로는) 서로 같다.