[問題] 排序時間複雜度問題
1.在n筆資料的二元搜尋樹上搜尋一筆資料，在最差情況下，其時間複雜度為?
(a)O(log n) (b)O(n) (c)O(n log n) (d)O(n^2)
答案是b，請問為什麼不是a呢??不是應該為log2 n嗎??
再來是關於Merge Sort的問題
因為課本上寫到每經過一次合併需要比較O(n)次，總共需要O(log2N)次
所以複雜度為O(n log2n)
我想請問的是如果是4筆資料由小到大排序，如12、6、55、60
不是要比較3次嗎??
他課本的範例是如果有5個元素，請問需要經過幾次的合併才能完成
答案是log2 5 = 3(次)
不知是否有前輩能指教呢??謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.62.164.121
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：