作者eduzone (eduzone)
看板Grad-ProbAsk
標題二元搜尋次數
時間Sun Aug 12 22:42:03 2018
一陣列內有62筆資料
以二元搜尋最多需比較幾次?
時間複雜度為O(log2N)
最差次數1+(log2N)
擬答1+(log2*62)=19 (error!)
還請問正確計算方式
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.105.157
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1534084925.A.CAB.html
1F：推 miachen8604: ceiling(lg62) = 6 08/12 23:10
2F：推 y2j60537: 應該是ceiling(log(62+1))吧 08/12 23:37
3F：推 miachen8604: 樓上正確，我忘了要+1 08/12 23:45
4F：→ eduzone: log2N=62, ceiling N=6不知正確? 08/12 23:54
5F：推 wilson50101: 想問一下 如果bst是斜的是不是就是62次了 08/12 23:59
6F：推 EXPCDR: 樓上 他是問二元搜尋不是問二元搜尋樹 08/13 00:10
7F：推 EXPCDR: 二元搜尋樹最糟搜尋來到O(n)每錯 08/13 00:13