求解递归关系:T(n)= 3T(n/5)+ lgn*lgn

Question

Consider the following recurrence
T(n) = 3T(n/5) + lgn * lgn

What is the value of T(n)?

(A) Theta(n ^ log_5{3})
(B) Theta(n ^ log_3{5})
(c) Theta(n Log n )
(D) Theta( Log n )

Answer is (A)

我的方法:

lgn*lgn = theta(n)因为c2lgn <2*lglgn <c1*lgn对于某些n> n0

上图不等式如图所示,c2 = 0.1,c1 = 1

log_5 {3} <1,

因此,通过主定理,答案必须是theta(n),并且没有一个答案匹配.如何解决这个问题呢？？

Answer 1

你声称lg n*lg n =Θ(n)是假的.请注意,当n变为无穷大时,(lg n)²/n 的极限趋于0.你可以使用l'Hopital的规则看到这个:

lim _n→∞(lg n)²/n

= lim _n→ ∞2lg n/n

= lim _n→∞2/n

= 0

更一般地,使用类似的推理,您可以证明对于任何ε> 0 ,lg n = o(^nε).

让我们尝试使用主定理解决这种复发.我们看到有三个子问题,每个大小为n/5,所以我们应该看一下log ₅的值.由于(lg n)² = o(n ^{log ₅ 3}),我们看到递归是重底的并且可以得出结论,递归求解为O(n ^{log ₅ 3}),这是上面列表中的答案(A).

希望这可以帮助!

Answer 2

为了应用主定理，我们应该检查之间的关系

\n\n

n ^{log ₅ (3)} ~= n ^0.682和 (lg(n)) ²

\n\n

不幸的是 lg(n) ² != 2*lg(n)：lg(n ² ) 等于 2*lg(n)

\n\n

另外，在主定理中，如果 f(n) 是 O(n ^{log _b (a)-ε} )，或者 \xce\x98(n ^{log _b a} )：如果前者成立，我们可以应用情况 1，如果后者满足定理的情况 2。

\n\n

乍一看，它看起来不太可能 (lg(n)) ² = \xce\xa9(n ^0.682 )，所以让我们尝试证明 (lg(n)) ² = O(n ^0.682 )，即：

\n\n

∃ n ₀ , c ∈ N ⁺，使得对于 n>n ₀ , (lg(n)) ² < c * n ^0.682

\n\n

让我们两边都开平方根（假设 n > 1，不等式成立）

\n\n

lg(n) < c ₁ * n ^0.341，（其中 c ₁ = sqrt(c)）

\n\n

现在我们可以假设 lg(n) = log ₂ (n) （否则乘法因子可能会被我们的常数吸收 - 正如您所知，常数因子在渐近分析中并不重要）并对两边求幂：

\n\n

2 ^lg(n) < 2 ^{c ₂ * n 0.341} <=> n < 2 ^{c ₂ * n 0.341} <=> n < (n ^{2 0.341} ) ^{c ₂} <=> n < (n ^{2 0.341} ) ^{c ₂} <=> n < (n ^1.266 ) ^{c ₂}

\n\n

_{选择 c 2} = 1 且 n ₀ = 1立即成立

\n\n

^{因此，f(n) = O(n log _b (a)-ε} )确实成立，我们可以应用主定理的情况 1 ，并得出结论：

\n\n

T(n) = O(n ^{log ₅ 3} )

\n\n

结果相同，但更正式一点。

\n