作者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/cn.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