O(n) 和O(log2n)是什么意思？
答案:2 悬赏:80 手机版
解决时间 2021-12-24 17:54
- 提问者网友：动次大次蹦擦擦
- 2021-12-23 19:48
在长度为n的有序线性表中进行二分查找，最坏情况下的比较次数应该 是n 次吧 可是为什么书上的答案是 O(log2n)?
最佳答案
- 五星知识达人网友：独行浪子会拥风
- 2021-12-23 20:48
是有序线性表，二分查找，不可能比较n次啊，比较n次你等于是把整个线性表遍历了一遍。二分查找每次可以排除一半元素。
比如123456789，你要找2，首先查中间元素5，大于2，所以直接排除掉5右边的6789
然后在1234里继续二分查找。
每次排除1/2的元素，所以是O(log2n)
比如123456789，你要找2，首先查中间元素5，大于2，所以直接排除掉5右边的6789
然后在1234里继续二分查找。
每次排除1/2的元素，所以是O(log2n)
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯