Master Theorem 什么时候可以实际应用？
When can the Master Theorem actually be applied?
对此我很沮丧。
在 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 这样的页面，在页面底部，它提到了完全相同的循环，并说它可以用主定理解决，因为它属于 "extended case 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！是我错了还是论文错了？
谁能把矛盾说清楚，说清楚什么时候可以用大定理，什么时候不能用？多项式差分检查什么时候重要，什么时候不重要？扩展案例2是否可用，还是实际上违反了什么？
编辑：
我尝试直接从第二篇论文中解决递归 (e)，我得到：
T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2
这不是大θn^2 lg^2 n吗？
书上说不能用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
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的先决条件 - 确实适用，您可以使用它。
对此我很沮丧。
在 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 这样的页面，在页面底部，它提到了完全相同的循环，并说它可以用主定理解决，因为它属于 "extended case 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！是我错了还是论文错了？
谁能把矛盾说清楚，说清楚什么时候可以用大定理，什么时候不能用？多项式差分检查什么时候重要，什么时候不重要？扩展案例2是否可用，还是实际上违反了什么？
编辑：
我尝试直接从第二篇论文中解决递归 (e)，我得到：
T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2
这不是大θn^2 lg^2 n吗？
书上说不能用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
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的先决条件 - 确实适用，您可以使用它。