※ 引述《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)
大概就是这样。