二元搜尋次數

看板Grad-ProbAsk作者 (eduzone)時間7年前 (2018/08/12 22:42), 編輯推噓6(6推 0噓 1→)
留言7則, 5人參與, 7年前最新討論串1/1
一陣列內有62筆資料 以二元搜尋最多需比較幾次? 時間複雜度為O(log2N) 最差次數1+(log2N) 擬答1+(log2*62)=19 (error!) 還請問正確計算方式 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.105.157 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534084925.A.CAB.html
推
08/12 23:10, 7年前 , 1F
ceiling(lg62) = 6
08/12 23:10, 1F
推
08/12 23:37, 7年前 , 2F
應該是ceiling(log(62+1))吧
08/12 23:37, 2F
推
08/12 23:45, 7年前 , 3F
樓上正確，我忘了要+1
08/12 23:45, 3F
→
08/12 23:54, 7年前 , 4F
log2N=62, ceiling N=6不知正確?
08/12 23:54, 4F
推
08/12 23:59, 7年前 , 5F
想問一下 如果bst是斜的是不是就是62次了
08/12 23:59, 5F
推
08/13 00:10, 7年前 , 6F
樓上 他是問二元搜尋不是問二元搜尋樹
08/13 00:10, 6F
推
08/13 00:13, 7年前 , 7F
二元搜尋樹最糟搜尋來到O(n)每錯
08/13 00:13, 7F
‣ 更多 eduzone 的文章
文章代碼(AID): #1RS4Szoh (Grad-ProbAsk)