解决递归方程 T(n) = 2T(n/2) + n^4。

Question

我正在使用MIT课件和CLRS书籍《算法导论》进行学习。

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

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

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

Level 0: n^4

Level 1: 2(n/2)^4

Level 2: 4(n/4)^4

Level 3: 8(n/8)^4

该树有lg(n)个级别。因此，我认为递归应该是：

T(n) = Θ(n^4 lg n)

但是，如果我使用主定理，则得出：

T(n) = Θ(n^4)

显然这两者都不能正确。哪一个是正确的？我的推理错在哪里？

- huherto

Answer 1

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

n^4 + 2(n/2)^4 + 4(n/4)^4 + ... + 2^i (n / 2^i)^4

但是2(n/2)^4≠n^4，因为(n/2)^4=n^4/16，所以2(n/2)^4=n^4/8。实际上，如果您计算数学，您会发现在第i级别上完成的工作由以下公式给出

n^4 / (2^-3i)

因此，我们得到(1+1/8+1/64+1/512+...)n^4，这可以证明小于2n^4。因此，您的函数为Θ(n^4)。

- templatetypedef

---

啊，我看到了我的错误。关于为什么它小于2n^4的解释很好。谢谢。 - huherto

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)

it is Θ(n^4)

- user467871

Answer 3

你可以直接使用主定理。

这个方程适用于主定理的第一种情况，其中log (a)基于b < f(n)

a：递归次数 b：子部分数量

log a基于b = log 2基于2 = 1 < n^4

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

- CyprUS

Answer 4

通过主定理

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

第一步 - 计算 n^(以 b 为底 a 的对数) => n(以 2 为底 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)

- Amit