Re: [問題] decision tree高度
看板Prob_Solve (計算數學 Problem Solving)作者yr (Light be with you)時間10年前 (2014/10/31 12:19)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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://www.ptt.cc/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
推
10/31 14:58, , 1F
10/31 14:58, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
