Question

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

Answer 1

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