看板 [ Prob_Solve ]
討論串[問題] decision tree高度
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] decision tree高度
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者jb679123 (又跳禎)時間10年前 (2014/10/31 12:00), 編輯資訊
1
0
1
內容預覽:
請問一下. 對n個元素做排序的話. 不論使用什麼comparsion sort. decision tree的高度恆為Ω(nlogn)嗎??. 想了一下不知道要怎麼解釋.... --. ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.214.127. ※ 文章網址: http:
#2
Re: [問題] decision tree高度
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者yr (Light be with you)時間10年前 (2014/10/31 12:19), 10年前編輯資訊
0
0
1
內容預覽:
n 個元素排序，則有 n! 個可能，所以至少 tree 要有. n! 個 leaf nodes (因為 sorting 結果在 leaf nodes)。. 再考慮 binary tree ，最佳狀況是 complete binary. tree ，不過考慮 full binary tree 可以有的
(還有387個字)
首頁
上一頁
1
下一頁
尾頁