Question

如果一个算法的时间复杂度可表示为：T(n)=2T([n/2])+1,请问它的复杂度是多少?

Answer 1

解析：由时间代价严格推出时间复杂度比较复杂,对于这种题,可用特例验证,不过需要注意的是特例不能取太少,至少n取到5,这样规律基本就可以确定了.

T(1)=1

T(2)=2T(1)+2=4

T(3)=2T(1)+3=5

T(4)=2T(2)+4=12

T(5)=2T(2)+5=13

很容易排除D选项,其递增速率介于O(n)和O(nsup>2)之间,故选nlogn,log以2为底.