[Algorithms] 비교 기반 sort의 worst case의 lower bound 분석

뭔가 제목이 깨끗하지는 않지만 
말 그대로이다.

key값의 비교를 기반으로 하는 sort의 worst case의 lower bound가 n log n 이라는 것을 수학적으로 보일 수 있다.

먼저 Decision tree는 yes or no를 선택하는 과정을 tree로 나타낸 것으로
여기에서는 키 값의 비교가 어떠한 decision이 된다.
즉, sort가 진행되는 과정을 decision tree로 나타낼 수 있다.

n lgn이 lower bound라는 것을 증명하기 위해서는 몇가지 lemma 필요하다.
lemma는 이미 참으로 증명된 정리로써 정리를 증명하는데 사용된다.

첫째, 키값을 기반으로 하는 모든 결정적 정렬 알고리즘의 decision tree는 n! 개의 leaves를 가진다.
둘째, binary tree의 depth d와 리프의 개수 m의 관계는 다음과 같다.   d ≥ lg m의 ceiling function
셋째, decision tree에서의 비교횟수의 worst case는 tree의 depth와 같다.
넷째, lg n! ≥ nlgn - 1.45n 

위의 렘마에 의하면
decision tree는 binary tree이기 때문에 lemma 1과 2에 의해
키값 비교기반의 정렬 알고리즘의 decision tree의 depth d와 노드의 갯수 n의 관계는
d  ≥ lg(n!)의 ceiling function 가 된다.
또한, 4번째 Lemma에 의해 d ≥ lg(n lgn - 1.45n)의 ceiling function이 되고
둘째 Lemma에 의해 depth가 곧 키 비교기반 알고리즘의 worst case 이므로

키 비교기반 정렬 알고리즘의 worst case의 Lower bound는 n lg n이 된다.