#5 알고리즘 Sorting Algorithms : Lower bounds for sorting

비교기반의 정렬알고리즘은 어떤 경우에도 O(n logn)보다 빠를 수 없습니다. 이를 증명하하는것으로 Sorting 부분은 넘어가도록 하겠습니다. Insertion Sort, Heap Sort, Quick Sort, Counting Sort, Radix Sort, Bucket Sort등등은 인터넷상에 자료가 많습니다. 혹시라도 잘 모르시는분들은 찾아서 해보시면 되겠습니다. 

Sort가 진행되는 과정은 Decision Tree로 나타낼 수 있습니다. 증명에는 몇가지 Lemma(참으로 증명된 정리)가 필요합니다. 

1. 모든 정렬 알고리즘의 decision tree는 n!개의 Permutation(순열)을 가진다. 

(다시말해, 정렬이 될 수 있는 모든 경우의 수가 n!이란 뜻입니다. )

2. Binary tree의 높이 d는 leaf의 개수를 m개라고 했을때 logm보다 같거나 크다

(기본적인 Binary tree의 정의입니다)

3. Decision tree에서의 비교횟수의 worst case는 Decision tree의 높이와 같다

(Decisiton tree를 이용해 정답을 찾기 위해서는 Decision tree의 높이만큼 연산해야 합니다)

4. Log(n!) ≥ nlogn - 1.45n

(증명)

Decision tree는 Binary Tree입니다. 따라서 lemma 1과 2에의해 Decision Tree의 깊이 d와  노드의 개수 n은 d ≥ log(n!) 입니다. 또한 lemma4에 의해 d ≥ nlogn - 1.45n가 되게 됩니다. 그리고 lemma3에 의해 높이가 곧 비교기반 알고리즘의 worst case이므로 lower bound는 위 비교식의 우측항의 가장 높은 차수인 nlogn이 됩니다. 

아무리 빠른 알고리즘을 구현한다고 하더라도 키값을 비교해야하는 비교기반 정렬 알고리즘의 시간복잡도는 nlogn 보다 적은 증가율을 가지는 함수가 될 수 없습니다.