[Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (2)

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다.

 

1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (1)

---

지난 글에 $x > k$에서 $\left| f(x)\right| \leq C\left|g(x)\right|$를 만족하는 상수 $k, C$가 존재하면 $f(x) = O(g(x))$라고 표현할 수 있었다고 하였다. (엄밀히 말하면 $f(x) \in O(g(x)))$이라 표현해야 한다. $O(g(x))$는 하나의 집합이기 때문이다.)

 

그럼, 이런 질문을 하여보자. 

$7x^2$은 $O(n^3)$인가?

생각해보면 $x > 7$ 일 때 $7x^2 < x^3$이므로 (부등식의 양변에 $x^2$를 곱하자.)

$C = 1, k = 7$ 로 생각하면 $7x^2$ 는 $O(x^3)$이라 생각할 수 있다.

 

그럼, $7x^2$은 $O(x^2)$도 가능하고, $O(x^3)$도 가능하면, 시간 복잡도를 분석하는 것이 무슨 의미가 있나? 또한, 이러한 일이 가능하다면 내가 예상했던 시간 복잡도보다 더 촘촘한 시간 복잡도가 없다는 것을 어떻게 증명해야 하는가? 분명 두 빅-오 표기법 상으로는 문제가 되지 않는 표기법이다. (이런 식으로 따지면 $7x^2$는 $O(x^5)$라고도 이야기할 수 있을 것이다. 틀린 말은 아니지만, 이렇게 말하면 시간 복잡도를 빅-오 표기법으로 이야기하는데 의미가 없을 것이다.)

 

그래서, 함수 $g$로는 가능한 한 "작은" 것을 선택해야 시간 복잡도 분석이 의미를 갖는다고 생각할 수 있다.

 

그럼, "작은"(좀 더 엄밀한) 것을 선택한다는 것은 어떻게 선택한다는 것일까? 직관적으로 이해할 순 있고 이미 널리 알음알음 사용되는 식들이 있지만, 하나씩 따져가면서 시간 복잡도를 이해해보자.

 

1. 다항식 / 다항함수의 시간 복잡도

다항식 및 다항함수는 시간 복잡도를 나타내는데 하나의 기준이 되는 함수이다. 다항 함수에 값을 대입하여 직접 얼마나 증가하는지 따지는 대신, 컴퓨터 공학자들은 다음과 같이 "작은" 것을 선택하도록 약속하였다.

---

$f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$ ($a_0 ,a_1 , \cdots , a_{n-1} ,a_n$은 실수) 라고 할 때, $f(x) = O(x^n)$ 이다.

---

 

이를 부등식을 이용하여 간단하게 증명하자. 삼각부등식에 의하여 $x > 1$에서

$$ \begin{align*}
\left|f(x)\right| &= \left|a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0\right|\\
&\leq \left| a_n \right| x^n + \left|a_{n-1} \right|x^{n-1} + \cdots + \left|a_1 \right|x + \left| a_0 \right|\\
&= x^n (\left|a_n \right| + \frac{\left|a_{n-1} \right|}{x} + \cdots + \frac{\left|a_0 \right|}{x^n})\\
&\leq x^n (\left|a_n \right| + \left|a_{n-1} \right| + \cdots +  \left|a_1 \right| + \left|a_0 \right|)
\end{align*} $$

라고 작성할 수 있고, 이는 $\left|f(x)\right| \leq Cx^n \quad(C = \left|a_n\right| + \left|a_{n-1}\right| + \cdots + \left|a_0\right|), \,\,\,\ k = 1$로 잡으면 되기에 $f(x) \in O(x^n)$이라 할 수 있다.

 

결국 다항함수에서의 가장 "작은" 함수는 최고차항의 차수에 의해 결정된다는 사실을 알 수 있다.

 

2. 다항식 / 다항함수 이외의 시간 복잡도

다항식 / 다항함수 이외의 시간 복잡도의 "작은" 함수의 기준으로 자주 쓰이는 함수들은 다음과 같은 함수들이 있다.

 

$$ 1,\,\, \log n,\,\,n ,\,\, n\log n,\,\,n^2, \,\,n!,\,\,2^n$$

 

예를 들어 보자.

$\log n!$ 의 Big-O notation은 어떻게 될까?

$n!$의 증가율은 무시무시하다. 이를 부등호를 이용하여 Big-O notation을 구하여보자.

 

$$\begin{align*}
\log n! &= \log (1\cdot2\cdot3\cdot\,\,\cdots\,\,\cdot n)\\
&=\log(1) + \log(2) + \log(3) +\cdots +\log(n)\\
&\leq \log(n) + \log(n) + \log(n) +\cdots +\log(n)\\
&= n\log(n)\\
\end{align*} $$

이므로 이를 정리하자면

$$ \begin{align*}
\log n! \,\leq\, n\log n
\end{align*}$$

이라고 할 수 있다. 따라서, $\log n!$은 $O(n\log n)$이라고 할 수 있고, 이때 $C = 1,\,k=1$이라 하면 된다.

 

이처럼 로그와 지수식 등 여러 방정식들로 식들을 근사 시키고, 상한선을 만들 수 있다. 또한, 이들을 적절히 조합하면 웬만한 문제들의 시간 복잡도를 계산하는데 문제가 없다고 선조들이 이어 왔다. (더 좋은 식이 있으면 수학과 컴퓨터계의 큰 이름을 남길 수 있을 것이다.)

 

시간 복잡도를 "작은" 함수들로 표현하는데 이해가 안 가는 부분이 없다면, 다음 글로 넘어가자.