主定理实际上可以在什么情况下应用？

Question

7

我对此感到非常沮丧。

在CLRS第三版的第95页（第4.5章）中提到，像 T(n) = 2T(n/2) + n lg n 这样的递归无法用主定理解决，因为差异 f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n 不是多项式。

但是我发现像这个网页底部提到完全相同的递归，并说它可以用主定理解决，因为它属于“扩展情况2”，尽管差异是非多项式的。它变成了n lg^2 n（将f(n)上的对数因子增加一）。

然后我遇到了这个页面，在示例（e）中似乎是扩展情况2的明显应用（递归是T(n) = 4T(n/2) + n^2 lg n），但解决方案不是n^2 log^2 n，而是n^2 log n！我错了还是论文错了？

请问有人能够澄清这些矛盾之处，并非常明确地说明什么时候可以使用主定理，什么时候不可以？多项式差异检查什么时候重要，什么时候不重要？扩展情况2是否可用，或者它是否实际上违反了什么？

编辑：

我尝试直接从第二篇论文中解决递归（e），我得到： T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2 这不是大O符号n^2 lg^2 n吗？

- AJJ

请注意，书中的Master Theorem的第二种情况与您在其他地方（包括您的示例）遇到的广义形式不同。广义形式从何而来？书中的Exercise 4.6-2，实际上很容易自己证明。 :-) - Michael Foukarakis

@MichaelFoukarakis你认为多项式差分规则只适用于情况1和3吗？ - AJJ

多项式差分“规则”比多对数情况更严格。它适用于所有3种情况。在第2种情况下，可以简单地放宽。 - Michael Foukarakis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这本书指出，无法使用Case 3解决它：

尽管它看起来具有适当的形式：...你可能会错误地认为应该应用第三种情况

然而，这个递归公式可以使用主定理的第二种情况来解决。

T(n) = 2T(n/2) + nlgn:

我们定义：

a = 2, b = 2, f(n) = nlgn

c = log_2(2) = 1
k = 1

而且f(n)确实在Theta(nlogn)中。

因此，所有主定理第二种情况的条件都适用，我们可以推断：

T(n)在Theta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)中。

长话短说，主定理有三种情况。每种情况都有其适用的先决条件。第三种情况具有更复杂的先决条件，因为它还需要收敛性。由于此公式不满足第三种情况的先决条件，因此您不能使用第三种情况。但是，第二种情况的先决条件确实适用，您可以使用它。