정보 이론적 하한 편집하기 (부분)

==비교 기반 정렬의 정보 이론적 하한==
n개의 원소를 정렬하는 경우 가능한 순열의 수는 n!이며, 정렬 알고리즘은 이 중 하나의 순서를 결정해야 한다. 따라서 결정 트리 모델을 이용하여 다음과 같이 하한을 유도할 수 있다.
*정렬 가능한 경우의 수: '''n!'''
*결정 트리의 리프 노드 개수: '''n!'''
*깊이가 d인 결정 트리는 최대 '''2<sup>d</sup>'''개의 리프 노드를 가질 수 있다.
*따라서, 다음 부등식을 만족해야 한다.
**n! ≤ 2<sup>d</sup>
*Stirling 근사를 사용하면,
**d = Ω(n log n)
즉, 비교 기반 정렬 알고리즘은 최적화하더라도 Ω(n log n)보다 빠르게 정렬할 수 없다. 

예를 들어 6개의 원소가 있다고 한다면, 

* 결정 트리의 리프는 최소 6!개가 필요
** 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
* 깊이가 d인 트리는 2<sup>d</sup>개의 리프노드를 가지므로
** 720 = 2<sup>d</sup>
** log<sub>2</sub>720 = 약 9~10 
** 깊이가 약 9.x 보다 커야 하므로
* 즉 깊이는 최소 10이어야 한다.
* 따라서, 6개의 원소를 정렬하려면, 최소 10번의 비교는 있어야 한다.