Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 递归方程组解的渐进阶的求法——套用公式法
发信站: 哈工大紫丁香 (2002年03月22日14:41:22 星期五), 站内信件

递归方程组解的渐进阶的求法——套用公式法
这个方法为估计形如：
T(n)=aT(n/b)+f(n) (6.17)
的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是
一个确定的正函数。
(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模
均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，
得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成
a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。

这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确
定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.1
7)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们
有T(n)的渐近估计式：
若对于某常数ε>0，有
，
则
；
若
，
则
；
若对其常数ε>0，有
且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。
这里省略定理的证明。
在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个
定理。读者可能已经注意到，这里涉及的三类情况，都是拿f(n)与作比较。定理直观地
告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数
较大，则T(n)=θ()；在第三类情况下，函数f(n)较大，则T(n)=θ(f (n))；在第二类情
况下，两个函数一样大，则T(n)=θ()，即以n的对数作为因子乘上f(n)与T(n)的同阶。

此外，定理中的一些细节不能忽视。在第一类情况下f(n)不仅必须比小，而且必须是多
项式地比小，即f(n)必须渐近地小于与的积，ε是一个正的常数；在第三类情况下f(n)
不仅必须比大，而且必须是多项式地比大，还要满足附加的“正规性”条件：af(n/b)≤
cf(n)。这个附加的“正规性”条件的直观含义是a个子间题的再分解和再综合所需要的
时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项
式为界的函数基本上都满足这个正规性条件。
还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况
和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况
和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落在这
两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。
下面是几个应用例子。
例1 考虑
T(n)=9T(n/3)+n0
对照(6.17)，我们有a=9，b=3， f(n)=n， ，取，便有，可套用第一类情况的公式，得
T(n)=θ(n2)。
例2 考虑
T(n)=T(2n/3)+1
对照(6.17)，我们有a=1，b=3/2， f(n)=1，，可套用第二类情况的公式，得T(n)=θ(l
ogn)。
例3 考虑
T(n)=3T(n/4)+nlogn
对照(6.17)，我们有a=3，b=4， f(n)=nlog n， ，只要取，便有。进一步，检查正规性
条件：
只要取c=3/4，便有af(n/b)≤cf(n)，即正规性条件也满足。可套用第三类情况的公式，
得T(n)=θ(f(n))=θ(nlogn)。
最后举一个本方法对之无能为力的例子。
考虑
T(n)=2T(n/2)+nlogn
对照(6.17)，我们有a=2，b=2， f(n)=nlog n， ，虽然f(n)渐近地大于，但f(n)并不是
多项式地大于，因为对于任意的正常数ε，
，
即f(n)在第二类情况与第三类情况的间隙里，本方法对它无能为力。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]