基于比较的排序算法的复杂度证明

http://hpc.ee.ntu.edu.tw/~ydlin/Ver2/psrs/index.html

以为很麻烦，今天上课听骆老师讲了一下，也不麻烦，挺有意思的。
A lower bound for the worst case

在decision tree裡，由root到各個leaf的路徑中最長的就是這個演算法在worst-case下所要做之比較的次數。顯然，這就是這個decision tree的高度(height)。也就是說，decision trees之高度的lower bound，也將是所有比較型排序演算法所需執行時間的lower bound。


Theorem: Any decision tree that sorts n elements has height Ω(n log n).

證明：

假設一個對n個輸入做排序的decision tree，其高度為h。由於n個輸入就會有n!種permutations，所以此decision tree至少必須有n!個leaves。而高度為h之binary tree至多只有2h個leaves，所以

n!≦2h

兩邊取對數，得到

h≧log(n!)

由Stirling’s approximation: