折半查找法的时间复杂度是什么？
答案:2 悬赏:40 手机版
解决时间 2021-02-11 16:12
- 提问者网友：藍了天白赴美
- 2021-02-10 17:11
折半查找法的时间复杂度是什么？
最佳答案
- 五星知识达人网友：煞尾
- 2021-02-10 18:07
时间复杂度为O(log2n)
全部回答
- 1楼网友：白昼之月
- 2021-02-10 18:37
假设对n个元素的折半查找需要消耗的时间为t(n)。容易知道：
如果n = 1，则t(n) = c1
如果n > 1，则t(n) = t(n/2) + c2
其中n/2需要取整，c1、c2都是常数
对于正整数n，可以有：
t(n) = t(n/2) + c2
= t(n/4) + 2*c2
= t(n/8) + 4*c2
= ...
= t(n/(2的k次方)) + k*c2
一直推演下去，直到n/(2的k次方)等于1，也就是k = log2(n)，此时等式变为：
t(n) = t(1) + k*c2
= c1 + log2(n)*c2
于是时间复杂度为log2(n)。注意log2(n)和log(n)其实是同样的复杂度，因为它们之间仅仅差了一个常量系数而已。
这个是不严格的推导，因为没有考虑整数除以2之后可能有余数的情况。但即使有余数，也是不影响时间复杂度的。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯