logo

비교 정렬 알고리즘 시간 복잡도의 하한 📂알고리즘

비교 정렬 알고리즘 시간 복잡도의 하한

정리

비교 정렬 알고리즘의 시간복잡도는 아무리 좋아도 Ω(nlog⁡n)\Omega ( n \log n ) 이다.

설명

알고리즘이 원래 신기한 것이지만, 삽입 정렬과 같은 효율적인 알고리즘도 퀵 정렬에 밀리는 것을 보면 그 이상의 알고리즘도 있지 않을까 궁금할 수밖에 없다. 다행인지 아닌지는 모르겠으나, 이 증명에 따라 그보다 효율적인 알고리즘을 생각할 필요는 없다.

물론 일반적인 비교 알고리즘이 아니라 특수한 조건이 주어진다면 이보다 더 빠른 알고리즘도 있다.

증명

크기가 nn 인 데이터가 주어졌다고 하자. 데이터가 나열될 수 있는 모든 경우의 수는 순열로 계산했을 때 n!n! 이 된다. 이 중 올바르게 정렬된 경우는 하나인데, nn 개의 데이터 중 두 개를 비교할 때마다 그와 같지 않은 나머지 경우의 수 절반을 배제할 수 있다. 다음의 예시로 이해해보자.

가령 세 개의 데이터 x1x_{1}, x2x_{2}, x3x_{3} 가 주어져 있다면 나올 수 있는 경우의 수는 3!=63! = 6 으로, 다음과 같이 여섯가지 경우의 수가 있다. (x1,x2,x3)(x1,x3,x2)(x2,x1,x3)(x2,x3,x1)(x3,x1,x2)(x3,x2,x1) ( 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} ) 위의 설명에 따라 x2<x1x_{2} < x_{1} 임을 확인하는 순간 이에 위배되는 절반의 경우는 배제하고 다음의 세 가지 경우만 남는다. (x2,x1,x3)(x2,x3,x1)(x3,x2,x1) ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{2} , x_{1} ) 만약 x1<x3x_{1} < x_{3} 이면 비교 정렬 알고리즘은 (x2,x1,x3)( x_{2} , x_{1} , x_{3} ) 을 반환하고 끝내고, x3<x1x_{3} < x_{1} 이면 마지막으로 x2x_{2} 과 x3x_{3} 를 비교해서 제대로 정렬된 경우를 반환해야한다.

이렇게 비교 정렬 알고리즘은 비교를 통해 경우의 수를 절반씩 줄일 수 있는데, 경우의 수를 어느정도 줄였는데도 부족한 정보가 있어 정렬을 끝내지 못했다면 최악의 경우 ⌈log⁡2n!⌉≈log⁡n!\left \lceil \log_{2} n! \right \rceil \approx \log n! 번을 계산해야한다.

스털링 근사: lim⁡n→∞n!enln⁡n−n2πn=1 \lim_{n \to \infty} {{n!} \over {e^{n \ln n - n} \sqrt{ 2 \pi n} }} = 1

스털링 근사에 따라 n!≈enlog⁡n−n2πn\displaystyle n! \approx e^{n \log n - n } \sqrt{ 2 \pi n } 이므로 log⁡n!=log⁡enlog⁡n−n2πn=nlog⁡n−n+log⁡2πn=nlog⁡n−n+12log⁡n+12log⁡2π=Ω(nlog⁡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*}

■