[이산수학]정렬 알고리즘의 한계

정렬 알고리즘은 데이터를 특정 순서로 나열하는 알고리즘이다. 여러 가지 정렬 알고리즘이 존재하며, 각 알고리즘은 서로 다른 특징과 성능을 가지고 있다. 하지만 모든 (비교 기반) 정렬 알고리즘은 절대로 $\mathcal{O}(n\log n)$보다 좋은 성능을 낼 수 없다.

 

증명

우선 데이터들이 총 $n$개가 주어진다고 하자. 그렇다면 만들 수 있는 $n$-튜플의 경우의 수는 총 $n!$개이다. 이 가운데 단 하나만이 올바른 순서쌍이 될 것이다. ($(a_1,\cdots,a_n)$에 대해, $1\le i\le j\le n\implies a_i\le a_j$인 튜플) 결정 트리의 최소 높이가 $\log n!=\sum_{k=1}^n\log k$이므로 다음 관계식을 만족한다.

$$\int_1^{n-1}\log xdx<\sum_{k=1}^n\log k<\int_1^n\log xdx$$

위 관계식을 정리하면 다음과 같다.

$$(n-1)\log (n-1)+2<\sum_{k=1}^n\log k<n\log n-n+1$$

$ (n-1)\log (n-1)+2$와 $ n\log n-n+1$은 모두 시간 복잡도 $\mathcal{O}(n\log n)$에 속하므로, $ \sum_{k=1}^n\log k$ 또한 $\mathcal{O}(n\log n)$에 속한다는 것을 알 수 있다. 따라서 모든 (비교 기반) 정렬 알고리즘은 적어도 시간 복잡도 $\mathcal{O}(n\log n)$에 속한다.