6

我对此感到非常沮丧。

在 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吗?

4

1 回答 1

3

该书指出,使用案例 3无法解决该问题:

即使它看起来有正确的形式:...您可能错误地认为案例 3 应该适用


然而,这个递推公式可以使用主定理解决,案例 2。

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

我们定义:

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

使用主定理案例 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)


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

于 2016-01-03T18:46:01.610 回答