※ 引述《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) 大概就是这样。 -- Some people are born on third base and go through life thinking they hit a triple. - Barry Switzer --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.126.251.25 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414729162.A.EC4.html ※ 编辑: yr (59.126.251.25), 10/31/2014 12:20:57 ※ 编辑: yr (59.126.251.25), 10/31/2014 12:25:46