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

Question

我正在尝试使用替代法解决递归问题。该递归关系式为：

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

我猜测 T(n) 是Θ(nlogn)，并且根据主定理，我很确定这一点，并且要找到上限，我使用归纳法。我试图表明 T(n)<= cn^2logn，但是这样做行不通。

我得到了 T(n)<= cn^2logn+n^2。然后我试图表明，如果T(n)<=c1n^2logn-c2n^2，则它也是O(n^2logn)，但是这也没有成功，我得到了T(n)<= c1n^2log(n/2)-c2n^2+n^2。

我应该如何解决这个递归问题呢？

- yrazlik

---

应该放在 http://cs.stackexchange.com/ 上。 - Oliver Charlesworth

如果你因为主定理而对解决方案有把握，那么问题到底是什么？主定理已经足够了（提示：你对主定理的使用是错误的）。 - SomeWittyUsername

@icepack 我需要用代入法来解决它，因为这是我的作业问题。 - yrazlik

Answer 1

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

当 2k 等于 n 时，过程停止。
⇒ k = log2n
⇒ T(n) = O(n2logn)

- SomeWittyUsername

Answer 2

你可以将方程重写为非递归形式。

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

- Artem Sobolev