二元搜尋次數

作者: eduzone (eduzone)   2018-08-12 22:42:03
一陣列內有62筆資料
以二元搜尋最多需比較幾次?
時間複雜度為O(log2N)
最差次數1+(log2N)
擬答1+(log2*62)=19 (error!)
還請問正確計算方式
作者: miachen8604 (這個U戲有必勝法)   2018-08-12 23:10:00
ceiling(lg62) = 6
作者: y2j60537 (skkkkuu)   2018-08-12 23:37:00
應該是ceiling(log(62+1))吧
作者: miachen8604 (這個U戲有必勝法)   2018-08-12 23:45:00
樓上正確,我忘了要+1
作者: eduzone (eduzone)   2018-08-12 23:54:00
log2N=62, ceiling N=6不知正確?
作者: wilson50101 (我覺得我還不錯啊)   2018-08-12 23:59:00
想問一下 如果bst是斜的是不是就是62次了
作者: EXPCDR (EXPCDR)   2018-08-13 00:10:00
樓上 他是問二元搜尋不是問二元搜尋樹二元搜尋樹最糟搜尋來到O(n)每錯

Links booklink

Contact Us: admin [ a t ] ucptt.com