用迭代法求解 T(n)=4T(n/2)+n

Question

我正在尝试使用迭代方法解决重复问题。我知道解决方案应该是 θ(n^2) 但我无法用迭代方法解决它。

这是我得到的结果：

T(n) = 4T(n/2)+n
T(n) = 4(4T(n/4)+n/2)+n
T(n) = 4(4(4T(n/8)+n/4)+n/2)+n

我不知道如何计算总和。我希望有人能帮助我。

提前致谢！

Answer 1

您可以通过与您相同的方式轻松地对其进行近似：

T(n) = 4T(n/2)+n                  
T(n) = 4(4T(n/4)+n/2)+n         =  4^2 T(n/4)     + 2n + n
T(n) = 4(4(4T(n/8)+n/4)+n/2)+n  =  4^3 T(n/8)     + 4n + 2n + n
                                  |--first part--|--second part--|

首先，由于迭代每次减半，然后本次迭代发生 log(n) 轮最大。

现在是第一部分，在第 i 轮之后是 4^i，因此它将来自 O(4^log(n)) = O(n^2)。

第二部分是几何系列n+2n+4n+8n....+n*2^i=n*(2^(i+1)-1)。因此 log(n) 回合的摊销时间将为 O(n*2^log(n))=O(n^2).

由于两部分都是O(n^2)，并且它们相加，所以total的摊销时间也是O(n^2)。

Answer 2

让我们定义 k 使得 2^k = n（^ 代表提升权力）。所以我们有

T(n) = 4 * T(n / 2) + n

作为

T(2^k) = 2^2 * T(2^(k-1)) + 2^k

让我们放松它：

T(2^k) = 2^2 * T(2^(k-1)) + 2^k =
       = 2^4 * T(2^(k - 2)) + 2^(k + 1) + 2^k =
       = 2^6 * T(2^(k - 3)) + 2^(k + 2) + 2^(k + 1) + 2^k =
       = 2^8 * T(2^(k - 4)) + 2^(k + 3) + 2^(k + 2) + 2^(k + 1) + 2^k = 
         ...
       = T(0) * (2^(2 * k) + ... + 2^(k + 2) + 2^(k + 1) + 2^k) =
       = T(0) * (2^k * (2^k + 2^(k - 1) + ... + 4 + 2 + 1)) = 
       = T(0) * (2^k * (2 * 2^k - 1))

从 k 到 n return 的时间；因为我们有 2^k = n:

T(n) = T(0) * n * (2 * n - 1)

有了 T(n) 的近似公式，我们可以很容易地计算出 θ:

    θ(T(0) * n * (2 * n - 1)) = 
  = T(0) * θ(n * (2 * n - 1)) =
  = 2 * T(0) * θ(n^2) =
  = θ(n^2)

用迭代法求解 T(n)=4T(n/2)+n

Solving T(n)=4T(n/2)+n with iterative methode

iteration

algorithm

complexity-theory