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

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

 

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

---

$$ \huge Thinking \quad about \quad Big-O$$

저번 글에서 빅-오 표기법을 "작은" 함수들로 나타내는 법을 다루었었다. 자주 사용하는 "작은" 함수들을 통해 시간 복잡도를 나타내었고, 이를 수식적으로 증명하였다.

 

실생활에서는 하나의 알고리즘이 아닌, 여러 알고리즘이 복합적으로 쓰이는 경우가 많다. 정렬을 하고 원하는 숫자를 찾는다던가, 누적 합을 여러 번 구해 가장 큰 합을 찾는 경우 등등 여러 알고리즘이 쓰이는 경우 어떻게 시간 복잡도를 산출해야 할까?

 

모든 알고리즘을 수식적으로 나타내고, 이를 부등식으로 시간 복잡도를 구하면 계산에 시간이 아주 많아 소요될 것이다.

 

생각해보자. 어떤 문제를 풀기 위해 사용되는 여러 알고리즘들을 나열하면, 그중 가장 느린 알고리즘이 있을 것이고, 가장 빠른 알고리즘이 있을 것이다.

 

직관적으로 생각해보면 입력이 매우 클 때, 가장 느린 알고리즘의 수행 시간과 연산 횟수는 상대적으로 빠른 다른 알고리즘의 수행 시간 및 연산 횟수에 비해 매우 클 것이고, 이는 가장 느린 알고리즘의 시간 복잡도만 고려해도 되고, 나머지 알고리즘의 시간 복잡도는 무시할 정도로 작다는 결론에 이르게 된다.

 

이를 수식적으로 증명하여 보자.

 

1. 두 알고리즘의 합

먼저, 두 개의 알고리즘이 순차적으로 사용되었다고 가정해보자.

 

$f_1(x) \in O(g_1(x))$ 이고 $f_2(x) \in O(g_2(x))$이라고 가정하자.

 

빅-오 표기법의 정의에 의하면, $x > k_1$일 때 $\left|f_1(x)\right| \leq C_1 \left|g_1(x)\right|$이고 $x > k_2$일 때 $\left|f_2(x)\right| \leq C_2 \left|g_2(x)\right|$를 만족하는 상수 $C_1, \,C_2,\,k_1,\,k_2$가 존재한다고 할 수 있다.

 

두 개의 알고리즘이 순차적으로 사용되었다는 것은 두 개의 연산 횟수의 합을 구해야 한다는 의미이므로, $f_1(x)$과 $f_2(x)$의 합을 부등식을 이용해 시간 복잡도를 추측해야 한다는 의미로 이어질 수 있다.

 

이를 수식적으로 추측하면 다음과 같다.

 

$$\begin{align*}
\left|(f_1 +f_2)(x) \right| &= \left|f_1 (x) + f_2(x)\right|\\
&\leq \left|f_1(x) \right| + \left|f_2(x) \right|\\
&\leq C_1 \left|g_1(x) \right| + C_2 \left|g_2(x) \right|\\
&\leq C_1 \left|g(x) \right| + C_2 \left|g(x) \right| \quad (g = \max(g_1,\,g_2))\\
&= (C_1 +C_2) \left|g(x) \right|\\
&= C \left|g(x) \right| \quad (C = C_1 +C_2)
\end{align*}$$

 

따라서, $x > k$일 때 $\left|(f_1 +f_2)(x) \right|\, \leq\, C \left| g(x) \right|$ 로 나타낼 수 있는 상수 $k,\,C$가 존재한다.

($k = \max(k_1,\,k_2),\quad C = C_1 + C_2$)

 

이를 정리하면 다음과 같다.

---

$f_1(x) = O(g_1(x))$이고, $f_2(x) = O(g_2(x))$일 때,

$(f_1 + f_2)(x)$ 는 $O(\max(\left|g_1(x)\right|,\,\left|g_2(x) \right|))$이다.

---

두 알고리즘의 합은 결국 더 큰 증가속도를 갖는 함수의 속도를 따라간다고 생각할 수 있다.

 

구체적으로 설명하면, 지수적으로 증가하는 알고리즘 ($O(2^n)$) 과 선형적으로 증가하는 알고리즘 ($O(n)$)이 순차적으로 사용된다면, 총 시간 복잡도는 지수 알고리즘을 고려해야 한다는 의미이다.

 

2. 두 알고리즘의 곱

두 알고리즘이 중첩적으로 사용될 경우를 생각해보자. 가령 조합적으로 여러 개의 수를 뽑는다던가, 탐색 범위를 줄여나가며 수를 찾는 경우 어떻게 해야 할까?

 

마찬가지로, $f_1(x) \in O(g_1(x))$ 이고 $f_2(x) \in O(g_2(x))$이라고 가정하자.

 

또한, $x > k_1$일 때 $\left|f_1(x)\right| \leq C_1 \left|g_1(x)\right|$이고 $x > k_2$일 때 $\left|f_2(x)\right| \leq C_2 \left|g_2(x)\right|$를 만족하는 상수 $C_1, \,C_2,\,k_1,\,k_2$가 존재한다고 할 수 있다.

 

이제, 두 알고리즘이 중첩된 경우, 즉 $f_1f_2(x)$의 시간 복잡도를 구하여보자.

 

$x > \max(k_1,\,k_2)$에 대하여 다음 부등식이 성립한다.

 

$$\begin{align*}
\left|(f_1 f_2)(x) \right| &= \left|f_1(x) \right| \left|f_2(x) \right|\\
&\leq C_1 \left|g_1(x) \right| C_2 \left|g_2 (x) \right|\\
&\leq C_1 C_2 \left|(g_1g_2)(x) \right|\\
&\leq C \left|(g_1 g_2) (x) \right|\quad(C = C_1 C_2)
\end{align*}$$

 

따라서, 위 부등식을 만족하는 상수 $C = C_1 C_2,\,\, k = \max(k_1,\,k_2)$가 존재하므로 $f_1(x) f_2(x)$의 시간 복잡도는 $O(g_1 g_2 (x))$라 할 수 있다.

 

이를 정리하면 다음과 같다.

---

$f_1(x) = O(g_1(x))$이고, $f_2(x) = O(g_2(x))$일 때,

$(f_1 \cdot f_2)(x)$ 는 $O(g_1 (x) g_2 (x))$이다.

---

두 알고리즘의 곱은 함수 증가속도의 곱이라 생각하면 된다.

 

구체적으로 설명하자면, 선형 시간 알고리즘 ($O(n)$)과 로그 시간 알고리즘 ($O(\log n)$)이 중첩된다면 이 알고리즘의 시간 복잡도는 두 알고리즘의 곱인 선형 로그 시간 알고리즘 ($O(n\log n)$)이 된다고 이야기할 수 있다.

 

이를 $n$개의 알고리즘으로 일반화하면 다음과 같다. 이에 대한 증명은 두 함수씩 짝지어서 하면 된다.

---

$f_1(x) = O(g_1(x))$, $f_2(x) = O(g_2(x))$, $\cdots$, $f_n(x) = O(g_n(x))$일 때,

$(f_1 + f_2 + \cdots + f_n)(x)$ 는 $O(\max(\left|g_1(x)\right|,\,\left|g_2(x) \right|,\cdots, \left|g_n(x)\right|))$이고, 

$(f_1 \cdot f_2\cdots f_n)(x)$ 는 $O(g_1 (x) g_2 (x)\cdots g_n(x))$이다.

---

따라서, 어떤 알고리즘의 총 시간 복잡도를 고려할 때는

 

1) 먼저 중첩된 알고리즘을 고려하여 각 부분별 알고리즘의 시간을 구하고

2) 부분별 알고리즘을 합쳐 가장 큰 알고리즘의 시간 복잡도를 구한다.

 

라고 정리할 수 있겠다.

 

그럼, "작은" 함수들($\log n,\, n,\, n\log n,\, n^2,\,\cdots$) 중 어떤 것이 더 크고 작은 알고리즘일까? 이를 다음 글에서 알아보자.