※ 引述《jb679123 (又跳禎)》之銘言：
: 請問一下
: 對n個元素做排序的話
: 不論使用什麼comparsion sort
: decision tree的高度恆為Ω(nlogn)嗎??
: 想了一下不知道要怎麼解釋...
n 個元素排序，則有 n! 個可能，所以至少 tree 要有
n! 個 leaf nodes (因為 sorting 結果在 leaf nodes)。
再考慮 binary tree ，最佳狀況是 complete binary
tree ，不過考慮 full binary tree 可以有的 leaf
nodes 比同樣高度的 complete binary tree 多（或一
樣），在第 x 層( x = 1, 2...) leaf nodes 數量
為 2^(x-1) 。
綜合以上， n! = 2^(x-1) 是最佳狀況，
x = Ω(log(n!)+1) = Ω(log(n^n)+1) = Ω(nlogn)
大概就是這樣。