求解递推式 T(n) = 2T(n/2) + n^4

Question

我正在使用 MIT 课件和 CLRS 书籍算法简介进行学习。

我目前正在尝试解决递归问题（来自第 107 页）

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

如果我制作一个递归树，我得到：

0级：n⁴

级别 1 2(n/2)⁴

2级4(n/4)⁴

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^{4< /sup>/8。事实上，如果你计算一下数学，你就会发现在级别 i 所做的工作由下式给出}

n⁴ / (2^-3i)

所以我们得到 (1 + 1/8 + 1/64 + 1/512 + ... ) n^{4< /sup>，可以显示小于 2n4。所以你的函数是 θ(n4)。}

Answer 2

通过递归，它是 θ(n^4)，

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

T(n) = 8*T(n/8) + n^4*(1 + 1/(2^3) + 1/(2^6))
...

T(n) = 2^k*T(n/(2^k)) + n^4*(1+ 1/(2^3) + 1/(2^6) + 1/(2^9)...+ 1/((2^(k-1))^3)

We know T(1) = 1

n = 2^k so k = log2(n) Then

T(n) = n*T(1) + n^4*( 1 - (1/(2^3))^k)/(1-1/8)

T(n) = n + (8/7)*n^4*(1 - n^(-3))

T(n) = n + (8/7)*(n^4 - n)

T(n) = (8/7)*n^4 - (1/7)*n


Θ(T(n)) = Θ((8/7)*n^4 - (1/7)*n)
Θ(T(n)) = Θ(n^4)

它是 θ(n^4)

Answer 3

这里可以直接使用主定理。

该方程适合主定理的情况 1，其中 log (a) 底 b f(n)

a：重复次数
b : 子部分的数量

log a base b = log 2 base 2 = 1 n^4

因此根据马斯特斯定理，T(n) = theta(f(n)) = theta(n^4)

Answer 4

根据主定理

a=2, b=2, f(n)=n^4

第一步 - 计算 n^(log a to base b) => n(以 2 为底的 log 2) = n*1 = n
第二步-是否f(n)>？第一步结果=> n^4> n =>是的
这意味着使用主定理的情况 3。

第三步 - 检查正则条件

a. f(n/b) <= c. f(n) where c>1 
a(n/b) . log(n/b) <= c. f(n)
2.(n/2) . log(n/2) <= c. n^4
n.log(n/2) <= c.n^4

是的，正则条件满足，所以我们的解决方案必须满足。

T(n) =theta (f(n)) = theta(n^4)