二元搜寻次数 eduzone PTT批踢踢实业坊

楼主: 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)每错

继续阅读