요즘 백준 온라인 저지에서 문제를 하나씩 풀고 있습니다. 재밌더군요. 좀더 어릴 때부터 이를 해왔다면 더 좋지 않았을까 생각합니다. 주위에 문제 해결 분야를 열심히 연습하는 친구들이 많이 있는데, 그 친구들이 생각하는 건 확실히 남다른 것 같더라고요. 저도 그런 실력을 갖췄다면 어땠을까 생각하며 부러워하기도 합니다. 여튼 지금부터라도 한다면 도움이 되지 않을까요?
아무튼 백준 문제를 풀다 보니 정렬 알고리즘을 사용해야할 때가 자주 있었습니다. 그리고 그때마다 저 나름대로 퀵 정렬(quick-sort)을 구현해왔습니다.(<algorithm>의 std::sort()가 그렇게 좋다는 사실은 최근에야 알게 되었습니다. 지금은 직접 안 짭니다. 하하.) 그러다 문득 퀵 정렬의 시간 복잡도 분석이 궁금해졌습니다. 대학생 때 퀵 정렬이 최악의 경우에는 \( O(n^2) \)의 시간 복잡도를 갖지만, 확률적으로는 \( O(n \log n) \)의 시간 복잡도를 가진다고 배웠습니다. 당시에는 그렇구나 하고 넘어갔는데, 지금 돌이켜 보니 그 분석이 어떻게 되는지 궁금해졌습니다.
교과서를 몇 권 훑어 보니 다양한 증명 방법이 많이 소개되어 있더군요. 그 중에서 개인적으로는 가장 간단하다고 생각되는 방법을 이번 포스트에서 소개하고자 합니다.
문제 정의
여기서 다룰 문제는 어떤 수열 \(a_1, \cdots, a_n\)이 주어졌을 때, 이를 오름차순으로 정렬하는 것입니다. 여기서 수열의 모든 수는 서로 다르다고 가정하겠습니다. 이렇게 가정해도 괜찮은 이유는 수열에 중복된 값이 있어도 위치값을 함께 저장하면 서로 다르게 만들 수 있기 때문입니다. 다시 말해, \(a_1, \cdots, a_n\)이 주어졌을 때, \[ \left[ \begin{array}{c} a_1 \\ 1 \end{array} \right], \left[ \begin{array}{c} a_2 \\ 2 \end{array} \right], \cdots, \left[ \begin{array}{c} a_n \\ n \end{array} \right] \]으로 표현하는 것이죠. 여기서 \( \left[ \begin{array}{c} a_i \\ i \end{array} \right] < \left[ \begin{array}{c} a_j \\ j \end{array} \right] \)일 조건은 \( a_i < a_j \)이거나 \(a_i = a_j \text{ & } i < j \)입니다. 그러면 위치값이 모두 서로 다르다는 성질을 통해서 이렇게 만들어진 수열도 모두 서로 다른 값을 갖는다는 것을 알 수 있습니다.
퀵 정렬 동작 방식
이 포스트는 퀵 정렬을 잘 아시는 독자를 대상으로 쓰여졌습니다. 따라서 퀵 정렬이 어떻게 동작하고 어째서 수열을 정렬해 주는지에 대해서는 자세히 설명하지 않겠습니다. 간략하게나마 알고리즘이 동작하는 것을 설명하자면 다음과 같습니다. 수열 \( a_1, \cdots, a_n \)에 대해 임의의 축(pivot) \(x\)를 하나 선정합니다. 이제 \(x\)보다 작은 값을 갖는 수를 \(a_1^\prime, \cdots, a_{i - 1}^\prime\), 반대로 \(x\)보다 큰 값을 갖는 수를 \( a_{i + 1}^\prime, \cdots, a_n^\prime \)이라고 하고, 각 부분 수열을 \(x\)의 앞과 뒤에 각각 배치합니다. 그러고 난 후 각 부분 수열을 재귀적으로 정렬하면 알고리즘이 완료됩니다.
수열의 길이가 \(n\)일 때 알고리즘이 수행되는 시간을 \(T(n)\)이라고 하겠습니다. 이 값은 어떤 축을 선택하냐에 따라 큰 폭으로 바뀌게 됩니다. 예를 들어, 매 재귀 호출마다 주어진 수열의 중간값(median)을 축으로 선정했다면, \[ T(n) = \left\{ \begin{array}{ll} \displaystyle O(1), && \text{if } n \leq 1,\\ \displaystyle 2 T( \frac{n}{2} ) + \Theta (n), && \text{otherwise} \end{array} \right. \]의 점화식을 얻게 되고, 이를 풀면 \( T(n) = O(n \log n) \)이라는 사실을 알 수 있습니다. 하지만 매번 가장 큰 값이나 가장 작은 값을 축으로 선택한다면, \[ T(n) = \left\{ \begin{array}{ll} \displaystyle O(1), && \text{if } n \leq 1,\\ \displaystyle T( n - 1 ) + \Theta (n), && \text{otherwise} \end{array} \right. \]의 점화식을 만들 수 있고, \(T(n) = O(n^2)\)이라는 결과를 얻게 됩니다.
따라서 퀵 정렬의 시간 복잡도는 어찌 보면 \(O(n^2)\)입니다. 즉, 최악의 경우에도 \(O(n \log n)\)의 시간 복잡도를 갖는 병합 정렬(merge-sort)이나 힙 정렬(heap-sort)보다도 느린 시간 복잡도를 갖는 것이죠. 그럼에도 퀵 정렬은 이름 그대로 일반적인 상황에서 가장 효율적인 정렬 방법으로 알려져 있습니다. 과연 이론적으로는 수행 시간이 더 좋아질 여지가 없는 것일까요?
여기서 확률을 도입한다면 이론적으로도 훨씬 좋은 결과를 얻을 수 있습니다. 확률이 어디에 어떻게 적용되면 될까요? 네, 그렇죠. 앞에서도 축이 시간 복잡도에 중요한 역할을 하였듯이, 축을 선택하는 작업을 확률적으로 진행하면 퀵 정렬의 시간 복잡도를 크게 향상시킬 수 있을 것입니다. 따라서 다음과 같은 알고리즘을 생각해 보겠습니다.
알고리즘 1. Randomized quick-sort
입력: 수열 \(a_1, \cdots, a_n\)
출력: 정렬된 수열
- 만약 \(n \leq 5\)이면, 직접 정렬된 수열을 구하고 종료한다.
- 그렇지 않다면, 주어진 수열에서 균일한 확률(uniformly at random)로 \(x\)를 선택한다.
- 이를 축으로 \( A_{\leq x} := \{a_1^\prime, \cdots, a_{i - 1}^\prime, x\} \)와 \( A_{> x} := \{a_{i + 1}^\prime, \cdots, a_n^\prime\}\)으로 수열을 쪼개고 각각 재귀적으로 정렬한다.
아래에서는 이 알고리즘의 수행 시간의 기댓값이 \(O(n \log n)\)이라는 사실을 보이도록 하겠습니다. 참고로 아래에서 분석하기 편하도록 단계 1에서 기저 조건을 \(n \leq 5\)로 잡았습니다.
조화수(Harmonic number)
분석을 위해서는 조화수(harmonic number)를 알아야 합니다. 이는 다음과 같이 정의됩니다.
정의 1. 조화수
\(n\)-번째 조화수 \(H_n\)은 \[ H_n := 1 + \frac{1}{2} + \cdots + \frac{1}{n} = \sum_{k = 1}^n \frac{1}{k} \]이다.
조화수의 흥미로운 성질 중 하나는 자연 로그를 근사한다는 점입니다. 그리고 이 사실은 알고리즘 1의 시간 복잡도를 분석할 때 요긴하게 사용됩니다.
정리 1. 조화수와 자연 로그의 관계
\( H_n = \Theta( \ln n ) \)이다.
확률 퀵 정렬 시간 복잡도 분석
이제 이번 포스트의 주된 내용인 확률 퀵 정렬의 시간 복잡도를 분석해 보겠습니다. 엄밀히 말하면, 알고리즘 1은 축을 어떻게 선택하는지에 따라서 수행 시간이 달라지게 되므로 그 기댓값을 구하도록 하겠습니다.
알고리즘 1이 어떻게 동작하는지 좀더 면밀히 살펴 보죠. 먼저 단계 1에서 수열의 길이 \(n\)이 \(5\)보다 작거나 같을 때에는 직접 정렬된 수열을 구합니다. 수열의 길이가 상수이므로 이를 구하는데 필요한 시간도 상수의 시간이 걸리게 됩니다. 이 경우 수행 시간의 최댓값을 상수 \(c\)라고 하겠습니다.
이제 \(n > 7\)인 경우입니다. 편하게 표현하기 위해서 \( a_1, \cdots, a_n \)을 정렬한 수열을 \(b_1, \cdots, b_n\)이라고 하겠습니다. 다시 말해, \( \{a_1, \cdots, a_n \} = \{ b_1, \cdots, b_n \} \)이면서 \( b_1 < \cdots < b_n \)을 만족합니다. 단계 2에 의해서 각 \(b_i\)가 \(x\)로 선정될 확률은 정확히 \(\frac{1}{n}\)입니다. 이때 단계 3에 의해 \[ A_{\leq x} = \{b_1, \cdots, b_{i - 1}, x\}, \quad A_{> x} = \{ b_{i + 1}, \cdots, b_n \} \]으로 수열이 쪼개지고 각각이 재귀적으로 정렬이 됩니다. 여기서 \( |A_{\leq x}| = i \)와 \( |A_{> x}| = n - i \)라는 사실을 얻을 수 있습니다. 또한, 단계 3에서 \( A_{\leq x} \)와 \( A_{> x} \)로 쪼개는 작업은 선형 시간에 수행할 수 있으며, 그 시간의 상한을 \(d \cdot n\)이라고 하겠습니다.(여기서 \(d\)는 상수입니다.)
따라서 수열의 길이가 \(n\)일 때 알고리즘 1의 수행 시간의 기댓값을 \(T(n)\)이라고 했을 때, 위에서 얻은 사실을 조합하면 다음과 같은 점화식을 이끌어낼 수 있습니다.
\[ T(n) \leq \left\{ \begin{array}{ll} \displaystyle c, && \text{if } n \leq 5,\\ \displaystyle \frac{1}{n} \sum_{i = 1}^{n - 1} \left[ T(i) + T(n - i) \right] + d \cdot n, && \text{otherwise} \end{array} \right. \tag{1} \]
우리의 목표는 \( T(n) = O(n \log n) \)임을 증명하는 것입니다. 그리고 이는 조화수의 성질을 활용하면 그렇게 어렵지 않게 보일 수 있습니다.
정리 2. 점화식 풀기
어떤 상수 \(a \geq \max(c, 4d)\)에 대해서, \( T(n) \leq a \cdot n \cdot H_n \)을 만족한다.
[증명] \(n\)에 대한 귀납법으로 증명하겠습니다. 기저 조건(base case)은 \( a > c \)이므로 쉽게 보일 수 있습니다. 이제 \(k < n\)에 대해서 \(T(k) \leq a \cdot k \cdot H_k\)를 만족한다고 가정하겠습니다. 먼저 식 1의 아랫줄을 약간 고치면 \[ T(n) \leq \frac{2}{n} \sum_{i = 1}^{n - 1} T(i) + d \cdot n \leq \frac{2a}{n} \sum_{i = 1}^{n - 1} i H_i + d \cdot n \tag{2}\]이 됩니다.
여기서 \( \sum_{i = 1}^{n - 1} i H_i \)의 항을 하나씩 나열해 보겠습니다.
\[ \begin{array}{rcccccccc} 1 \cdot H_1 & = & 1 \cdot 1 & & & & & & \\ 2 \cdot H_2 & = & 2 \cdot 1 & + & 2 \cdot \frac{1}{2} & & & & \\ & \vdots & & & & & & & \\ (n - 1) \cdot H_{n - 1} & = & (n - 1) \cdot 1 & + & (n - 1) \cdot \frac{1}{2} & + & \cdots & + & (n - 1) \cdot \frac{1}{n - 1} \end{array} \]
각 항을 더하는 순서를 가로가 아닌 세로로 하면 \(j\) 번째 열은 \[ [ j + \cdots + (n - 1) ] \cdot \frac{1}{j} = \left[ \frac{(n - 1) n}{2} - \frac{(j - 1)j}{2} \right] \cdot \frac{1}{j} \leq \frac{n^2}{2} \cdot \frac{1}{j} - \frac{j - 1}{2}\]을 만족하게 됩니다. 여기서 첫 번째 등식은 \(1\)에서 \(n - 1\)까지를 더한 것에서 \(1\)에서 \(j - 1\)까지를 더한 것을 뺀 것입니다. 이를 모두 더하면, \[ \sum_{i = 1}^{n - 1} i H_i \leq \sum_{j = 1}^{n - 1} \left[ \frac{n^2}{2} \cdot \frac{1}{j} - \frac{j - 1}{2} \right] = \frac{n^2}{2} H_{n - 1} - \frac{(n - 2)(n - 1)}{4} \tag{3}\]을 이끌어낼 수 있습니다.
식 3을 식 2에 대입하면, \[ T(n) \leq a n H_{n - 1} - \frac{a(n - 2)(n - 1)}{2n} + dn \]를 얻을 수 있습니다. \( H_{n - 1} < H_n \)임은 자명합니다. 또, \( a > 4d \)이고 \( n > 5 \)에 대해 \( \frac{2(n - 2)(n - 1)}{n} > n \)이기 때문에 위 식에서 마지막 두 항 역시 상쇄시킬 수 있습니다. 따라서 \( T(n) \leq a n H_n \)을 만족하게 되어 모든 증명이 완성됩니다. □
마치며
이것으로 확률 퀵 정렬의 시간 복잡도에 대한 내용을 모두 마치겠습니다. 본문의 분석을 통해 퀵 정렬에서 축을 균등한 확률로 선택한다면 수행 시간이 \( O(n \log n) \) 정도 될 것으로 기대할 수 있습니다. 하지만 이 알고리즘은 여전히 (그 확률은 극히 낮지만) \( O(n^2) \)에 수행할 여지가 남아있습니다. 매 재귀 호출마다 축을 멍청하게 선택할 가능성이 있으니 말이죠. 그렇다면 퀵 정렬로는 병합 정렬이나 힙 정렬처럼 최악의 경우에도 \( O(n \log n) \)의 시간 복잡도를 가질 수 없을까요?
만약 우리가 매 재귀 호출 때마다 주어진 수열의 중간값을 선형 시간에 결정론적으로(deterministically) 얻어낼 수 있다면 퀵 정렬은 최악의 경우에도 \( O(n \log n) \)이 될 것입니다. 그리고 놀랍게도 선형 시간에 수열의 중간값을 구하는 deterministic algorithm이 존재합니다. 다음 시간에는 그 알고리즘에 대해서 알아보도록 하겠습니다.
혹시 궁금하신 점이 있으시거나, 잘못된 사항이 발견되면 알려주시기 바랍니다. 고맙습니다. :)
참조
[1] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. New York: McGraw-Hill Higher Education, 2008.
'알고리즘 & 확률 > Sort & Selection' 카테고리의 다른 글
| 선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians) (4) | 2020.08.01 |
|---|
