解决重复性T（n）= 2T（n / 2）+ n ^ 4

Question

我正在使用MIT课件和CLRS书算法简介。

我目前正在尝试解决重复性问题（从第107页开始）

T（n）= 2T（n / 2）+ n ⁴

如果创建递归树，则会得到：

等级0：n ⁴

Level 1 2（n / 2）⁴

Level 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 ）[[4 = n [4 / 8。实际上，如果算出数学，就会知道在[i]级完成的工作是通过

n

4

/（2

-3i

）因此我们得到（1 + 1/8 + 1/64 + 1/512 + ...）n ⁴，可以证明小于2n

4

。因此您的函数是Θ（n ⁴）。

Answer 2

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) base 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 ^（以a为底的对数b）=> 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)