主题:折半查找的时间复杂度
永远的C
[专家分:0] 发布于 2010-10-10 17:55:00
想请教下,有谁知道折半查找的时间复杂度如何计算出来的,我只知道结果,不知道过程,请教下了
回复列表 (共1个回复)
沙发
eastcowboy [专家分:25370] 发布于 2010-10-12 11:50:00
假设对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之后可能有余数的情况。但即使有余数,也是不影响时间复杂度的。
我来回复