第1章 递归方程解的渐近阶的求法

《第1章 递归方程解的渐近阶的求法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录递归方程组解的渐进阶的求法——代入法1递归方程组解的渐进阶的求法——迭代法4递归方程组解的渐进阶的求法——套用公式法8递归方程组解的渐进阶的求法——差分方程法10递归方程组解的渐进阶的求法——母函数法14递归方程解的渐近阶的求法递归方程组解的渐进阶的求法——套用公式法这个方法为估计形如：T(n)=aT(n/b)+f(n)(6.17)的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f(n)是一个确定的正函数。(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模

2、为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。这个方法依据的是如下的定理：设a≥1和b≥1是常数f(n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么

3、，在f(n)的三类情况下，我们有T(n)的渐近估计式：1.若对于某常数ε>0，有，则；2.若，则；171.若对其常数ε>0，有且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。这里省略定理的证明。在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉及的三类情况，都是拿f(n)与作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数较大，则T(n)=θ()；在第三类

4、情况下，函数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个子间题的再分解和再综合所需要的时间最多与原问题的分解和

5、综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数基本上都满足这个正规性条件。还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落在这两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。下面是几个应用例子。例1考虑T(n)=9T(n/3)+n017对照(6.17)，我们有a=9，b=3，f(

6、n)=n，，取，便有，可套用第一类情况的公式，得T(n)=θ(n2)。例2考虑T(n)=T(2n/3)+1对照(6.17)，我们有a=1，b=3/2，f(n)=1，，可套用第二类情况的公式，得T(n)=θ(logn)。例3考虑T(n)=3T(n/4)+nlogn对照(6.17)，我们有a=3，b=4，f(n)=nlogn，，只要取，便有。进一步，检查正规性条件：只要取c=3/4，便有af(n/b)≤cf(n)，即正规性条件也满足。可套用第三类情况的公式，得T(n)=θ(f(n))=θ(nlogn)。最后举

7、一个本方法对之无能为力的例子。考虑T(n)=2T(n/2)+nlogn对照(6.17)，我们有a=2，b=2，f(n)=nlogn，，虽然f(n)渐近地大于，但f(n)并不是多项式地大于，因为对于任意的正常数ε，，即f(n)在第二类情况与第三类情况的间隙里，本方法对它无能为力。递归方程组解的渐进阶的求法——差分方程法17这里只考虑形如：T(n)=c1T(n-1)+c2T(n-2)+…+ckT(n-k)+f(n)，n≥k(6.18)的递归方程。其中ci(i=l，2，…，k)为实常数，且ck≠0。它可改写为一

8、个线性常系数k阶非齐次的差分方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=f(n)，n≥k(6.19)(6.19)与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅，这里直接给出(6.19)的解法，略去其正确性的证明。第一步，求(6.19)所对应的齐次方程：T(n)-c1T(n-1)-c2T(n-2)-…-ckT(n-k)=0(6.20)的基本解系：写出(6.20)的特征方程：C