Question

已知某递归算法的复杂度为:T(n)=2T(n/2)+4,则求解该递归式的解为:

有没有大佬给答案的？

Answer 1

4(2n-1)

可以这样理解，递归分解到最后一层是n个四
上一层是n/2个4，再上一层n/4个4，一直往上
全部加起来是2n-1个4
时间复杂度忽略掉常数是O(n)的

追问

答案是错的

追答

噗，这玩意谁知道他让写4(2n-1)啊还是8n-4啊还是O(n)。。。会算就行了，这种试题没啥意义

Answer 2

T(n)=2T(n/2)+4
n=2m时
2T(n/2)+4
2(2T(n/2/2)+4)+4
2(2(2T(n/2/2/2)+4)+4)+4
2^log2(n)T(1)+4*2^0+2*4^1+2^(log2(n)-1)

Answer 3

O(n)

网页链接