여기서는 알고리즘의 시간복잡도를 표현하는 5가지 함수의 개념과 구분 방법에 대해 개략적으로 설명하고자 합니다.

시간복잡도 함수?

$\omega \ (small \ omega) - \Omega \ (Big \ Omega) - \Theta \ (Theta) - O \ (Big \ O) - o \ (small \ o)$

위의 5가지 함수들은, 특정한 알고리즘이 "최대", 혹은 "평균적으로", 혹은 "최악의 상황에는" 어느정도의 시간복잡도 내에서 수행되는지와 관련한 정보를 표현하기 위해 사용된다. 위의 순서대로 (혹은 반대의 순서대로) 기억하면 편한데, 어떠한 관계가 있는지 알아보자.

---

우리끼리의 용어 약속 : "차수적으로"

이러한 용어는 공적인 용어는 아닌 것으로 알고, 단순히 여기서 설명의 편의를 위해 사용하고자 한다.

함수 f가 g보다 "차수적으로" 크다
: $\lim_{n \to \infty}f/g = \infty$

함수 f가 g보다 "차수적으로" 작다
: $\lim_{n \to \infty}f/g = 0$

함수 f가 g보다 "차수적으로" 동일하다
: $\lim_{n \to \infty}f/g = c \ \ (c \ne 0)$

즉 함수 n이 발산함에 따라 f와 g의 비율이 0으로 수렴하거나 발산하면 차수적으로 차이가 있고, f와 g의 비율이 상수로 수렴하면 차수적으로 동일하다고 할 수 있다.

따라서 f가 g보다 "차수적으로" 크다 라는 말은,
n이 커짐에 따라 f가 g보다 "무한대의 비율로" 커짐을 의미한다. 즉 아무리 f가 g보다 크다 하더라도 그 비율이 무한대로 발산하지 않으면 f는 g보다 차수적으로 커지지 못한다.

• 이 말을 f는 g보다 더 큰 '카테고리'에 있다 라고도 할 수 있을 것 같다.

$f = 1000000000n^2+99999999999, g = 0.00000000001n^2$

어떻게든 f가 g보다 커보이게 하려고 노력하였으나, 둘의 최고차항은 동일하게 $n^2$이다. 따라서 f와 g는 차수적으로 동일하다.

$f = n, g = 3n^2 + 1$

위의 경우에는 f/g가 0으로 수렴한다. 따라서 차수적으로 g가 f보다 크다.

$f = e^n, g = log(n)$

위의 경우에 f/g는 무한대로 발산한다. 따라서 차수적으로 f가 g보다 크다.

여기까지 왔다면, 이제는 위의 5가지 시간복잡도 함수를 구분해 보자.

---

5가지 시간복잡도 함수 구분하기

• $g(n)$이 최상/최악/일반적인 경우에 어느 정도의 시간복잡도를 가지는지를 나타낸다.

1. $\omega \ (small \ omega)$

$g(n) \in \omega(f(n))$
= $g(n) > f(n)$
= $g(n)$이 $f(n)$ 보다 차수적으로 크다 (동일 차수에 있을 수 없다)

특정 함수 $g(n)$이 최상의 경우에도 "무조건" $f(n)$보다는 높은 수준의 시간복잡도를 가진다.

2. $\Omega \ (Big \ Omega)$

$g(n) \in \Omega(f(n))$
= $g(n) > or \approx f(n)$
= $g(n)$이 $f(n)$ 보다 차수적으로 크거나, 차수적으로 같다. (같을 수도 있음에 유의하자)

특정 함수 $g(n)$이 최상의 경우 $f(n)$ 수준의 시간복잡도를 가진다.
평균적으로는 $f(n)$보다 큰 시간복잡도를 가진다.

3. $\Theta \ (Theta)$

$g(n) \in \Theta(f(n))$
= $g(n) \approx f(n)$
= $g(n)$이 $f(n)$과 차수적으로 동일하다. (같은 차수를 가진다)
= $f(n)$ 는 $g(n)$과 점근적으로 동일하다. ($f(n) = g(n)$과는 다른 표현임을 생각하자)

특정 함수 $g(n)$이 평균적으로 어느 정도의 시간복잡도를 가지는지를 나타내기 위해 사용된다.

4. $O \ (Big \ O)$

$g(n) \in O(f(n))$
= $g(n) \approx or < f(n)$
= $g(n)$이 $f(n)$보다 차수적으로 같거나, 차수적으로 작다. (같을 수도 있음에 유의하자)
= $f(n)$ 는 $g(n)$과 점근적으로 동일하다.

특정 함수 $g(n)$이 최악의 경우 $f(n)$ 수준의 시간복잡도를 가진다.
평균적으로는 $f(n)$보다 작은 시간복잡도를 가진다.

5. $o \ (small \ o)$

$g(n) \in o(f(n))$
= $g(n) < f(n)$
= $g(n)$이 $f(n)$보다 차수적으로 작다. (동일 차수에 있을 수 없다)
= $f(n)$ 는 $g(n)$과 점근적으로 동일하다.

특정 함수 $g(n)$이 최악의 경우에도 "무조건" $f(n)$보다는 낮은 차수의 시간복잡도를 가진다.

사실 small-omega와 small-o는 일반적으로 잘 사용하지는 않는다. 함수의 성능에 있어서 지나치게 넓은 범위에서만 설명해 주기 때문이다.
일반적으로 많이 사용되는 함수는 2, 3, 4번의 $big-\Omega$, $\Theta$, $big-O$이다.
몇 가지 예시를 통해 개념을 정립하자.

---

시간복잡도 함수 예시

$n^2 + 10n \in \Omega(n^2)\ \ ?$
= 왼쪽이 오른쪽보다 큰 차수, 혹은 같은 차수인가? -> O

$n \in \Omega(n^2) \ ?$
= 왼쪽이 오른쪽보다 큰 차수, 혹은 같은 차수인가? -> X. 무조건 오른쪽이 더 크다.

위의 표현을 올바르게 고치려면, $\Omega$ 대신에 $o$ 혹은 $O$ 를 사용하면 된다.

$n \in o(n^2) \ ?$
= 오른쪽이 왼쪽보다 큰 차수인가? -> O

$n \in O(n^2) \ ?$
= 오른쪽이 왼쪽보다 큰 차수, 혹은 같은 차수인가? -> O

$n \in \Theta(n^2) \ ?$
= 오른쪽과 왼쪽은 같은 차수인가? -> X

---

차수 관계를 모르겠을 때 (뭐가 더 큰 거예요?)

처음에, 차수는 $n$이 발산함에 따라 두 함수 간의 비율이 어떻게 변화하는지를 토대로 크기를 비교한다고 설명하였다.
하지만 이러한 크기 관계가 명확하지 않은 경우가 발생한다. 이를테면 아래와 같은 경우이다.

1. $a^n \in o(n!)$ ? (단, $a$ > 1)

2. $n! \in o(n^n)$ ?

어렵다...! 이러한 함수들의 크기 비교는 수학적으로 충분히 가능하지만, 크기 비교를 신속하게 하기 위해서는 기본적인 함수들의 차수 관계를 알고 있을 필요가 있다.
기본적인 함수들의 대소 관계는 아래와 같다.

$logn < n < nlogn < n^a (a > 1) < a^n (a > 1) < n! < n^n$

위의 대소 관계를 1번과 2번 문제에 대해 적용해 보자.

1. $a^n \in o(n!)$ ? (단, $a$ > 1)
   -> 팩토리얼 함수는 지수함수보다 높은 차수에 있으므로, small-$o$ 관계가 성립한다.

2. $n! \in o(n^n)$ ?
   -> $n^n$ 함수는 팩토리얼 함수보다 높은 차수에 있으므로, small-$o$ 관계가 성립한다.