Control 版 (精华区)

发信人: doer (老三： 醉亦何妨), 信区: Control
标  题: 算法复杂性8(转载)
发信站: 哈工大紫丁香 (2002年06月08日10:41:59 星期六), 转信

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 longforyou 所发表 】
递归方程组解的渐进阶的求法——代入法
用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答
作出推测，然后用数学归纳法证明推测的正确性。

例如，我们要估计T(n)的上界，T(n)满足递归方程：



其中是地板(floors)函数的记号，表示不大于n的最大整数。

我们推测T(n)=O(nlog n)，即推测存在正的常数C和自然数n0，使得当n≥n0时有：

T(n)≤Cnlog n (6.2)

事实上，取n0=22=4，并取



那么，当n0≤n≤2n0时，(6.2)成立。今归纳假设当2k-1n0≤n≤2kn0 ，k≥1时，(1.1.16
)成立。那么，当2kn0≤n≤2k+1n0时，我们有：



即(6.2)仍然成立，于是对所有n≥n0，(6.2)成立。可见我们的推测是正确的。因而得出结
论：递归方程(6.1)的解的渐近阶为O(nlogn)。

这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。推测
递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。我们在这里提三点建议
：

(1) 如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合
理的。作为例子，考虑递归方程：



右边项的变元中加了一个数17，使得方程看起来难于推测。但是它在形式上与(6.1)很类似
。实际上，当n充分大时

与

相差无几。因此可以推测(6.3)与(6.1)有类似的上界T(n)=O(nlogn)。进一步，数学归纳将
证明此推测是正确的。

(2)从较宽松的界开始推测，逐步逼近精确界。比如对于递归方程(6.1)，要估计其解的渐
近下界。由于明显地有T(n)≥n，我们可以从推测T(n)=Ω(n)开始，发现太松后，把推测的
阶往上提，就可以得到T(n)=Ω(nlog n)的精确估计。

(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方程
，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。例如考
虑递归方程：



看起来很复杂，因为右端变元中带根号。但是，如果作变元替换m=logn，即令n=2m ，将其
代入(6.4)，则(6.4)变成：



把m限制在正偶数集上，则(6.5)又可改写为：

T(2m)=2T(2m/2)+m

若令S(m)=T(2m)，则S(m)满足的递归方程：

S(m)=2S(m/2)+m ，

与(6.1)类似，因而有：

S(m)=O(m1og m)，

进而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn) (6.6)

上面的论证只能表明：当(充分大的)n是2的正偶次幂或换句话说是4的正整数次幂时(6.6)
才成立。进一步的分析表明(6.6)对所有充分大的正整数n都成立，从而，递归方程(6.4)解
的渐近阶得到估计。

在使用代入法时，有三点要提醒：

(1)记号O不能滥用。比如，在估计(6.1)解的上界时，有人可能会推测T(n)=O(n)，即对于
充分大的n，有T(n)≤Cn ，其中C是确定的正的常数。他进一步运用数学归纳法，推出：



从而认为推测T(n)=O(n)是正确的。实际上，这个推测是错误的，原因是他滥用了记号O ，
错误地把(C+l)n与Cn等同起来。

(2)当对递归方程解的渐近阶的推测无可非议，但用数学归纳法去论证又通不过时，不妨在
原有推测的基础上减去一个低阶项再试试。作为一个例子，考虑递归方程



其中是天花板(floors)函数的记号。我们推测解的渐近上界为O(n)。我们要设法证明对于
适当选择的正常数C和自然数n0，当n≥n0时有T(n)≤Cn。把我们的推测代入递归方程，得
到：



我们不能由此推断T(n)≤Cn，归纳法碰到障碍。原因在于(6.8)的右端比Cn多出一个低阶常
量。为了抵消这一低阶量，我们可在原推测中减去一个待定的低阶量b，即修改原来的推测
为T(n)≤Cn-b 。现在将它代人(6.7)，得到：



只要b≥1，新的推测在归纳法中将得到通过。

(3)因为我们要估计的是递归方程解的渐近阶，所以不必要求所作的推测对递归方程的初始
条件（如T(0)、T(1)）成立，而只要对T(n)成立，其中n充分大。比如，我们推测(6.1)的
解T(n)≤Cnlogn，而且已被证明是正确的，但是当n=l时，这个推测却不成立，因为(Cnlo
gn)|n=1=0而T(l)>0。





--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 61.156.24.116]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shao.hit.edu.cn]