퀵소트(Quicksort)는 왜 시간복잡도가 평균 $O(n \log n)$일까?

증명하는 방법에는 여러가지가 있지만, 그 중에서도 기댓값(expectation)의 선형성(linearity)을 사용해서 깔끔하게 증명하는 방법을 소개하고자 합니다.

1. 기댓값의 선형성

두 랜덤 변수 $X$, $Y$에 대해, $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$가 성립합니다. 매우 익숙한 사실이죠.

증명은, 정의에 따라 수식을 차근차근 전개하면 됩니다:

$$ \begin{align} \mathbb{E}[X + Y] &= \sum_{x} \sum_{y} (x + y)p(x, y) \\ &= \sum_{x} \sum_{y} x p(x, y) + \sum_{x} \sum_{y} y p(x, y) \\ &= \sum_{x} \sum_{y} x p(x, y) + \sum_{y} \sum_{x} y p(x, y) \\ &= \sum_{x} x \sum_{y} p(x, y) + \sum_{y} y \sum_{x} p(x, y) \\ &= \sum_{x} x p(x) + \sum_{y} y p(y) \\ &= \mathbb{E}[X] + \mathbb{E}[Y]. \end{align} $$

심지어 $X$, $Y$가 독립이 아니더라도 상관이 없습니다! 증명에서 다음에 해당하는 부분은 일명 주변화(marginalization)로, 어떤 의미로는 결합 확률(joint probability)의 정의라고도 볼 수 있습니다:

$$ p(y) = \sum_{x} p(x, y). $$

이러한 두 랜덤 변수의 기댓값의 선형성은, 일반화를 시켜보면 다음과 같은 형태로도 쓸 수 있습니다:

$$ \mathbb{E} \left[ \sum_{i = 1}^{n} c_{i} X_{i} \right] = \sum_{i = 1}^{n} c_{i} \mathbb{E} \left[ X_{i} \right]. $$

한편으로, 분산의 경우는 어떻게 될까요? 마찬가지로 수식을 열심히 전개하면 다음과 같은 결과가 나옵니다:

$$ \mathbb{V} [X + Y] = \mathbb{V} [X] + \mathbb{V} [Y] + 2 \text{Cov}(X, Y). $$

여기서 Cov는 공분산(covariance)으로써, 두 변수가 독립이라는 가정이 있어야 공분산이 0이 되면서 선형성을 가질 수 있겠네요!

2. 베르누이 시행

동전 던지기와 같이, 총 두개의 가능성을 지닌 결과가 나오는 시행(trial)을 전통적으로 베르누이 시행(Bernoulli trial)이라고 부릅니다.

동전을 던져서 앞면이 나올 확률을 $p$, 뒷면이 나올 확률을 $1 - p$라 합시다. 또, $i$번째 시행때 앞면이 나온 경우 1, 뒷면이 나온 경우 0을 가지는 랜덤변수 $X_{i}$를 설정합시다. 각 시행은 서로 독립이고 같은 분포를 따른다고 가정하면 (이러한 가정을 independent and identical distribution, 약자로는 $i.i.d$라고 합니다) 총 $n$번 시행 했을때 앞면이 나온 경우의 수는 다음과 같이 구할 수 있습니다:

$$ X = \sum_{i = 1}^{n} X_{i}. $$

그럼 앞면이 대충(expected) 몇번쯤 나올까요? 기댓값 $\mathbb{E}[X]$를 직접 구하려면 아래와 같은 복잡한 식이 나오게 됩니다:

$$ \mathbb{E}[X] = \sum_{k = 0}^{n} k \binom{n}{k} p^{k} (1 - p)^{(n - k)}. $$

이 식은 물론 몇가지 트릭을 사용해서 계산 해볼 수는 있는데요, 기댓값의 선형성을 사용한다면 더욱 손쉽게 구할 수 있습니다:

$$ \mathbb{E}[X] = \mathbb{E} \left[ \sum_{i = 1}^{n} X_{i} \right] = \sum_{i = 1}^{n} \mathbb{E}[X_{i}]. $$

각 시행은 같은 분포를 따르기 때문에, 모든 $\mathbb{E}[X_{i}]$의 값이 같을 것입니다. 때문에, 딱 하나만 직접 구해봅시다:

$$ \mathbb{E}[X_{i}] = 1 \times p + 0 \times (1 - p) = p. $$

그럼 $X$의 기댓값은 이 $\mathbb{E}[X_{i}]$들의 합이므로, $\mathbb{E}[X] = np$가 되겠죠? 위에 나왔던 복잡한 식을 풀어서 계산하는 것보단 훨씬 간단한 방법입니다.

여담으로, 이 상황에선 각 시행이 서로 독립이기 때문에 분산 역시 선형성을 사용한 계산이 가능합니다:

$$ \mathbb{V}[X_{i}] = \mathbb{E}[X_{i}^{2}] - \mathbb{E}[X_{i}]^{2} = p - p^{2} = p(1 - p), $$

$$ \mathbb{V}[X] = \sum_{i = 1}^{n} \mathbb{V}[X_{i}] = np(1 - p). $$

사족으로, 총 $k$번의 앞면이 나왔을때 앞면이 나올 확률인 $p$의 값을 $k/n$으로 추정하는 것은 얼마나 그럴싸한 일일까요? 예컨대, 동전을 10번 던져서 앞면이 3번 나왔을때, "이 동전은 앞면이 나올 확률이 30%다!"라고 주장한다면, 그 주장은 얼마나 신뢰성 있는 주장이 될까요?

우리는 이미 랜덤변수 $X_{i}$와 $X$를 잘 설정했기 때문에, $k$는 곧 랜덤변수 $X$의 실현(realization)이 된다는걸 알 수 있습니다. 때문에, 아래와 같은 계산이 가능합니다:

$$ \mathbb{E} \left[ \frac{k}{n} \right] = p, $$

$$ \mathbb{V} \left[ \frac{k}{n} \right] = \frac{p(1 - p)}{n}. $$

분산에서 상수곱은 제곱으로 빠져나온다는 사실을 이용했습니다.

즉, $n$이 커질수록 $k/n$라는 추정은 더 정확해 진다는것을 알 수 있죠. $k/n$의 분산이 한없이 0으로 줄어들기 때문입니다! 이 재밌는 사실은 non-parametric estimation 기법 중 Parzen window method의 기초가 됩니다. 통계적 머신러닝 수업 시간에 자주 접하게 되는 친구죠.

3. 퀵소트의 시간복잡도

문제 세팅을 잘 한다면, 위와 같이 기댓값의 선형성을 사용해서 명료하게 퀵소트의 시간복잡도가 평균 $O(n \log n)$이라는 사실을 증명할 수 있습니다. "얼추 절반씩 감소하니까..."로 만족하기엔 약간 찝찝하죠.

퀵소트는 각 재귀호출마다 피벗(pivot)을 정해서 그 피벗의 값을 기준으로 정렬 대상인 부분배열을 작은 쪽과 큰 쪽으로 나눕니다. 이를 반복하다보면 정렬이 반드시 됩니다. 이 '반드시 된다'는 것에 대한 증명은 여기서는 생략하겠습니다. 생각보다 어렵지 않아요!

결국 핵심은 이 피벗을 어떻게 정하냐인데요, 일명 'median of medians'라 불리우는 엄청난 알고리즘을 사용해서 피벗이 항상 1사분위수(1st quantile)에서 ~ 3사분위수(3rd quantile) 사이쯤의 값이 되도록 할 수도 있습니다. 이 알고리즘은 구현하기는 번거롭지만, 퀵소트의 시간복잡도를 항상 $O(n \log n)$으로 만들수도 있습니다!

여기서는 그런 어려운 방법 말고, 구현하기 제일 쉬운 '랜덤 피벗 선택'을 생각하기로 합시다. 부분배열에서 피벗을 아무거나 하나 랜덤으로 정하는 방법이죠!

추가로, 정렬해야하는 데이터의 분포에 대한 정보가 없이, 값 비교만을 사용해서 정렬하는 상황이라고 가정합시다 - 데이터의 분포를 사용 할 수 있다면 더 빠르고 좋은 정렬 알고리즘이 존재할 수 있습니다. 버킷 정렬(bucket sort)이 대표적이죠.

다시 피벗 선택 얘기로 돌아와서 - 한번의 재귀호출에서 한번의 랜덤 피벗 선택이 이뤄집니다. 즉, 조금 다르게 해석을 하자면 이 '피벗 선택 수열(sequence)'의 길이가 전체 알고리즘의 수행 시간을 결정한다고 볼 수 있습니다. 운이 나쁘면 안좋은 피벗 즉 부분배열을 잘 가르지 못하게되고, 새로운 재귀호출을 야기하게 되겠죠. 피벗 선택을 또 해야하고, 피벗 선택 수열의 길이는 증가하고, 알고리즘의 수행 시간도 같이 증가하게 됩니다. 그러니 이 피벗 선택 수열(sequence)이란것에 집중해봅시다. 한 피벗 선택 수열을 $\sigma$라 하고, 이러한 $\sigma$들을 모두 모은 집합을 $\Omega$라 합시다. 확률론스럽게 해석을 하자면 $\sigma$는 랜덤한 무언가의 결과 혹은 가능성(event)이고, $\Omega$는 표본공간(sample space)가 되겠네요.

랜덤변수 설정을 해야하는데, $C(\sigma)$를 피벗 선택 수열 $\sigma$가 결정된 상황에서, 퀵소트 알고리즘이 수행하게 될 값 비교의 횟수라고 합시다. 이게 좀 헷갈릴 수 있는데, 랜덤변수의 정의는 언제까지나 표본공간에서 실수 혹은 정수 등으로 가는 함수입니다. 이 '비교 횟수'에 집중하는 이유는, 퀵소트에서 사용되는 모든 연산이 많아봤자 '비교 횟수'만큼만 일어나기 때문입니다.

그럼 이제 우리의 목표는 $\mathbb{E}[C] = O(n \log n)$이 된다는것을 보이는 것입니다. 즉, 시간복잡도의 평균이 $O(n \log n)$이 된다는 뜻이죠.

약간 헷갈릴 수 있으니 천천히 읽어주세요.

$z_{i}$를 배열에서 $i$번째로 작은 값이라 합시다. 또, 어떠한 $i < j$에 대해, 랜덤변수 $X_{ij}(\sigma)$를 "$\sigma$일때 $z_{i}$, $z_{j}$가 비교된 횟수"로 설정합시다. 그러니까, 예컨대 배열의 첫번째 값과 마지막 값은 퀵소트 알고리즘이 진행되면서 총 몇번이나 비교가 되었을까요? 하고 묻는 랜덤변수입니다. 편의를 위해 배열의 값이 모두 다르다고 가정합시다.

혹시 눈치 채셨나요? 아주 재밌는 점은, 이 랜덤변수 $X_{ij}(\sigma)$는 오직 0 혹은 1의 값만 가질 수 있다는 사실입니다. 왜냐면

1. 모든 '비교'는 오직 피벗하고만 일어난다.
2. 한번 '비교'된 피벗은 다시는 쓰이지 않는다.

라는 점 때문입니다. 때문에, 어떤 두 값은 운좋게도 비교가 안될수는 있어도, 2번 이상 비교 되는 일은 퀵소트 알고리즘 내에선 절대로 일어나지 않습니다! 헉, 혹시 심심하다면 최대 비교 횟수도 계산해볼 수 있겠네요.

이제 위에서 정의한 $C(\sigma)$를 정확하게 풀어서 써봅시다:

$$ C(\sigma) = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} X_{ij}(\sigma). $$

기댓값을 구하기에 아주 깔끔하고 손쉬운 식이죠. 왜냐면 위에서 소개했듯, 각 랜덤변수 $X_{ij}$가 독립이 아니더라도 기댓값의 선형성을 이용해서 합을 전개해버리면 되기 때문입니다. 편의상 $p_{ij} = \mathbb{E}[X_{ij}]$라 합시다. 이제 기댓값을 전개해봅시다:

$$ \mathbb{E}[C] = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \mathbb{E}[X_{ij}], $$

$$ \begin{align} \mathbb{E}[X_{ij}] &= 0 \times P(X_{ij} = 0) + 1 \times P(X_{ij} = 1) \\ &= P(X_{ij} = 1) \\ &=: p_{ij}. \end{align} $$

이제 저 괴상한 $p_{ij}$의 값을 구하고, 이를 모두 더해서 계산하는 일만 남았습니다! 스포일러부터 하자면, $p_{ij}$의 값은 놀랍게도 정확히 다음과 같습니다:

$$ p_{ij} = \frac{2}{j - i + 1}. $$

왜 그럴까요? 어떠한 $i < j$에서, $z_{i}$부터 $z_{j}$까지의 값들의 그룹을 생각해봅시다. 총 $(j - i + 1)$개의 원소가 있겠죠? 그럼 재밌게도, 만약 피벗이 이 안에서 선택되지 않는다면, 이 값들의 그룹은 통째로 왼쪽 혹은 오른쪽 재귀호출로 넘겨집니다 (피벗이 이 그룹의 최솟값보다 작거나 최댓값보다 크기 때문입니다). 즉, 그룹이 통째로 유지가 된다는 것이죠. 그와 동시에, 해당 재귀호출 상황에선 그룹 내 값들 끼리는 비교가 일어나지 않게 됩니다. 즉, 이렇게 피벗이 그룹 바깥에서 선택이 된 경우에는 $z_{i}$와 $z_{j}$가 비교 될 확률을 계산하는데 있어서 영향을 주지 않습니다.

그럼 $z_{i}$와 $z_{j}$가 비교 될 확률이란건 어떤 상황일까요? 바로 저 그룹 내에서 $z_{i}$ 혹은 $z_{j}$가 피벗으로 선택되었을때, 비로소 두 원소가 비교 됩니다. 위에서도 말했듯, '비교'라는 행위는 언제나 피벗하고만 이뤄지기 때문이죠. 이러한 상황이 일어날 확률이 바로 위에 있는 $p_{ij}$가 됩니다! 이 그룹에는 총 $(j - i + 1)$개의 원소가 있고, 그 중에서 $z_{i}$ 혹은 $z_{j}$가 선택이 되어야하기 때문에 저 값이 나오게 됩니다.

만약 이 그룹 내에서 $z_{i}$나 $z_{j}$가 아닌 값이 피벗으로 선택된다면, $z_{i}$와 $z_{j}$는 이제 다음 재귀호출부터는 완전히 다른 그룹으로 나눠질테고, 더이상 만나는 일은 영영 없게됩니다.

이제 이 $p_{ij}$ 값을 대입해서 계산하는 일만 남았습니다.

아까는 손쉽게 계산 할 수 있다고 말했는데, 막상 구해보니까 $p_{ij}$가 그다지 이쁜 모양은 아니네요? 근데 잘 생각해보면, 우리의 목적은 어디까지나 $\mathbb{E}[C] = O(n \log n)$을 보이는 것입니다. 즉, 평균의 상한을 구하면 되는것이죠. 그러므로 부등식을 사용해서 식을 좀 대충대충 만들어봅시다:

$$ \begin{align} \mathbb{E}[C] &= \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1} \\ &\leq \sum_{i = 1}^{n - 1} \sum_{k = 2}^{n} \frac{2}{k} \\ &\leq 2n \sum_{k = 2}^{n} \frac{1}{k} \\ &\leq 2n \log n. \end{align} $$

우리가 원하는 형태는 어떻게든 $n$과 $\log n$ 같은 인수가 등장하는 것이었기 때문에, 위와 같이 퉁치면 원하던 식을 이끌어낼 수 있습니다.

결과적으로 우리가 원하던 $\mathbb{E}[C] = O(n \log n)$이 나왔네요! 따라서, 퀵소트 알고리즘에서 피벗을 랜덤하게 대충 선택 해도, 평균적으로 $O(n \log n)$ 정도는 나온다는겁니다. 퀵소트는 비교 말고는 해야 할 일과 요구하는 공간이 매우 적기 때문에, 후딱 해치워서 평균 $O(n \log n)$이면 엄청난 결과입니다. 괜히 quick이라는 이름이 붙은게 아니죠!