algorithm - 求解 T(n) = 4T(n/2)+n²

Question

我正在尝试使用替换方法解决重复问题。递归关系为：

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

我的猜测是 T(n) 是 Θ(nlogn) （由于主定理，我对此很确定），为了找到一个上限，我使用归纳法。我试图证明 T(n)<=cn ² logn，但这不起作用。

我得到了 T(n)<=cn ² logn+n ²。然后我试图证明，如果 T(n)<=c ₁ n ² logn-c ₂ n ²，那么它也是 O(n ² logn)，但这也没有用，我得到了 T(n) <=c ₁ n ² log(n/2)-c ₂ n ² +n ² `。

我该如何解决这种复发？

Answer 1

T(n) = 4T(n/2) + n 2 
     = n 2 + 4[4T(n/4) + n²/4]
     = 2n 2 + 16T(n/4)
     = ...
     = k⋅n 2 + 4 k T(n/2 k )
     = ...

到达时该过程停止。 ⇒ ⇒2kn
k = log2n
T(n) = O(n2logn)

Answer 2

您可以以非递归形式重写您的方程式

您的递归方程非常简单：每次展开 T(n/2) 时，只会出现一个新项。因此，在非递归形式中，您将获得二次项的总和。你只需要证明 A(n) 是log(n)（我把它留给你作为一个简单的练习）。