推 fzrmitsul:謝謝a大 05/28 18:49
※ 引述《fzrmitsul (我的妹妹很可愛)》之銘言：
: 1.在n筆資料的二元搜尋樹上搜尋一筆資料，在最差情況下，其時間複雜度為?
: (a)O(log n) (b)O(n) (c)O(n log n) (d)O(n^2)
: 答案是b，請問為什麼不是a呢??不是應該為log2 n嗎??
在極端情況下
二元搜尋樹可能會退化成左(右)傾樹
這情況下是 O(n)
: 再來是關於Merge Sort的問題
: 因為課本上寫到每經過一次合併需要比較O(n)次，總共需要O(log2N)次
: 所以複雜度為O(n log2n)
: 我想請問的是如果是4筆資料由小到大排序，如12、6、55、60
: 不是要比較3次嗎??
: 他課本的範例是如果有5個元素，請問需要經過幾次的合併才能完成
: 答案是log2 5 = 3(次)
: 不知是否有前輩能指教呢??謝謝
1 2 3 4 5
[ ] [ ] [ ] step1
[ ] [ ] step2
[ ] step3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.63.88