algorithm - 求解递归 T(n) = 2T(n/2) + n^4

Question

我正在学习使用麻省理工学院课件和 CLRS 书算法导论。

我目前正在尝试解决复发问题(来自第107页)

T(n) = 2T(n/2) + n⁴

如果我创建一个循环树，我会得到:

Level 0: n⁴

Level 1 2(n/2)⁴

Level 2 4(n/4)⁴

Level 3 8(n/8)⁴

这棵树有 lg(n) 层。因此我认为复发应该是

T(n) = Θ(n⁴ lg n)

但是，如果我使用主定理，我就明白了

T(n) = Θ(n⁴)

显然这两种说法都不对。哪一个是正确的？我的推理哪里出了问题？

Answer 1

第二个看起来是正确的。请注意，您的循环树看起来像

n⁴ + 2(n/2)⁴ + 4(n/4)⁴ + ... + 2ⁱ (n / 2ⁱ)⁴

但是 2(n/2)⁴ ≠ n⁴，因为 (n/2)⁴ = n⁴/16，所以 2(n/2)⁴ = n⁴/8。事实上，如果你算出数学，你会得到第 i 级完成的工作由

n⁴ / (2^-3i)

所以我们得到 (1 + 1/8 + 1/64 + 1/512 + ... ) n⁴，可以证明它小于 2n^{4。所以你的函数是 Θ(n4)。}