algorithm - Master Theorem 什么时候可以实际应用？

Question

我对此很沮丧。

在 CLRS 第 3 版第 95 页(第 4.5 章)中，它提到像

T(n) = 2T(n/2) + n lg n

不能用主定理解决，因为差异

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

不是多项式。

但后来我遇到了像 this 这样的页面在页面底部，它提到了完全相同的循环，并说它可以用主定理解决，因为它属于“扩展案例 2”，即使差异是非多项式的。它变为 n lg^2 n(将 f(n) 上的对数因子增加一)。

然后我遇到像 this 这样的页面其中示例 (e) 似乎是扩展案例 2 的明确应用(重复是 T(n) = 4T(n/2) + n^2 lg n)，但解决方案是不是n^2 log^2 n，而是n^2 log n!是我错了还是论文错了？

谁能澄清矛盾并明确说明什么时候可以使用Master Theorem，什么时候不能使用？多项式差分检查什么时候重要，什么时候不重要？扩展案例 2 是否可用，或者它实际上是否违反了某些内容？

编辑:

我尝试直接从第二篇论文中解决递归 (e)，我得到:

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

这不是大 theta n^2 lg^2 n吗？

Answer 1

书上说不能用Case 3解决:

even though it appears to have the proper form: ... You might mistakenly think that case 3 should apply

---

然而，这个递归公式可以使用主定理求解，情况 2。

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

我们定义:

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

使用 Master theorem case 2 :

c = log_2(2) = 1
k = 1

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

因此，掌握定理案例 2 的所有条件都适用，我们可以推导出:

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

---

长话短说，大师定理有3个案例。每个案例都有其适用的先决条件。案例 3 的先决条件更复杂，因为它也需要收敛。
因为case 3的先决条件不适用于这个公式，你不能使用case 3。但是，case 2的先决条件 - 确实适用，你可以使用它。