我对此感到非常沮丧。
在 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
不是多项式。
但是后来我遇到这样的页面,在页面底部,它提到了完全相同的重复,并说它可以用主定理解决,因为它属于“扩展案例 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
这不是大θn^2 lg^2 n
吗?