비교 정렬 알고리즘 시간 복잡도의 하한
정리
비교 정렬 알고리즘의 시간복잡도는 아무리 좋아도 $\Omega ( n \log n )$ 이다.
설명
알고리즘이 원래 신기한 것이지만, 삽입 정렬과 같은 효율적인 알고리즘도 퀵 정렬에 밀리는 것을 보면 그 이상의 알고리즘도 있지 않을까 궁금할 수밖에 없다. 다행인지 아닌지는 모르겠으나, 이 증명에 따라 그보다 효율적인 알고리즘을 생각할 필요는 없다.
물론 일반적인 비교 알고리즘이 아니라 특수한 조건이 주어진다면 이보다 더 빠른 알고리즘도 있다.
증명
크기가 $n$ 인 데이터가 주어졌다고 하자. 데이터가 나열될 수 있는 모든 경우의 수는 순열로 계산했을 때 $n!$ 이 된다. 이 중 올바르게 정렬된 경우는 하나인데, $n$ 개의 데이터 중 두 개를 비교할 때마다 그와 같지 않은 나머지 경우의 수 절반을 배제할 수 있다. 다음의 예시로 이해해보자.
가령 세 개의 데이터 $x_{1}$, $x_{2}$, $x_{3}$ 가 주어져 있다면 나올 수 있는 경우의 수는 $3! = 6$ 으로, 다음과 같이 여섯가지 경우의 수가 있다. $$ ( x_{1} , x_{2} , x_{3} ) \\ ( x_{1} , x_{3} , x_{2} ) \\ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{1} , x_{2} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ 위의 설명에 따라 $x_{2} < x_{1}$ 임을 확인하는 순간 이에 위배되는 절반의 경우는 배제하고 다음의 세 가지 경우만 남는다. $$ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ 만약 $x_{1} < x_{3}$ 이면 비교 정렬 알고리즘은 $( x_{2} , x_{1} , x_{3} )$ 을 반환하고 끝내고, $x_{3} < x_{1}$ 이면 마지막으로 $x_{2}$ 과 $x_{3}$ 를 비교해서 제대로 정렬된 경우를 반환해야한다.
이렇게 비교 정렬 알고리즘은 비교를 통해 경우의 수를 절반씩 줄일 수 있는데, 경우의 수를 어느정도 줄였는데도 부족한 정보가 있어 정렬을 끝내지 못했다면 최악의 경우 $\left \lceil \log_{2} n! \right \rceil \approx \log n!$ 번을 계산해야한다.
스털링 근사: $$ \lim_{n \to \infty} {{n!} \over {e^{n \ln n - n} \sqrt{ 2 \pi n} }} = 1 $$
스털링 근사에 따라 $\displaystyle n! \approx e^{n \log n - n } \sqrt{ 2 \pi n }$ 이므로 $$ \begin{align*} \log n! =& \log e^{n \log n - n } \sqrt{ 2 \pi n } \\ =& n \log n - n + \log \sqrt{ 2 \pi n } \\ =& n \log n - n + {{1} \over {2}} \log n + {{1} \over {2}} \log 2 \pi \\ =& \Omega ( n \log n ) \end{align*} $$
■