如何通过迭代方法解决t（n）= t（n/2） + 2^n的递归复杂性？

Question

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

t（n）= 1 for n <= 4

我知道通用器官是：

t（n）= t（n/2^（i + 1）） +从i = 0到2^（n/2^i）的总和

---

从这里我不知道该如何进行。

Answer 1

您的符号有一些问题。一般器官应该是：

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

在此步骤之后，我们让 i = log(2, n) - 1, ， 以便 T(n/2^(i+1)) = T(1).

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

注意 sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) 是 2^n + 2^(n/2) + 2^(n/4) + ..., ，比 2^n + 2^(n-1) + 2^(n-2) + .... 。但是，后者是 2^(n+1) - 1. 。所以前者是两者之间 2^n 和 2^(n+1). 。因此， 和 是 O(2^n).

然后 T(n) = O(2^n).