[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..
Computer Science 2011. 7. 7. 20:59
1