algorithm - 解决递归关系 : 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 → ∞} 2 lg n / n

= lim _{n → ∞} 2 / n

= 0

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

让我们尝试使用主定理来解决这个递归问题。我们看到存在三个大小为 n/5 的子问题，因此我们应该查看 log₅ 3 的值。因为 (lg n)² = o(n ^{log₅ 3}), 我们看到递归是底部重的并且可以得出结论递归求解到 O(n^{log₅ 3})，这是上面列表中的答案 (A)。

希望这对您有所帮助!