algorithm - 如何通过迭代方法解决 T(n) = T(n/2) + 2^n 的递归复杂度？

Question

我试图找到上限和下限，这可能是 O(2^n)

对于 n<=4，T(n) = 1

我知道一般器官是：

T(n) = T(n/2^(i+1)) + 从 i=0 到 k of 2^(n/2^i) 的总和

---

从这里我不知道如何进行..

Answer 1

There is some problem with your notation. The general organ should be:

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

After this step, we let i = log(2, n) - 1, so that T(n/2^(i+1)) = T(1).

Therefore, T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

Note that sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) is 2^n + 2^(n/2) + 2^(n/4) + ..., which is smaller than 2^n + 2^(n-1) + 2^(n-2) + .... However, the latter stuff is 2^(n+1) - 1. So the former stuff is something between 2^n and 2^(n+1). Therefore, the sum is O(2^n).

Then T(n) = O(2^n).