※ 引述《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/m.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