搜索
1目录递归方程组解的渐进阶的求法——代入法....................................................................11递归方程组解的渐进阶的求法——迭代法..............................................................14递归方程组解的渐进阶的求法——套用公式法.......................................................17递归方程组解的渐进阶的求法——差分方程法.........................................................3递归方程组解的渐进阶的求法——母函数法.............................................................7递归方程解的渐近阶的求法递归方程组解的渐进阶的求法——套用公式法这个方法为估计形如：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.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：1.若对于某常数ε0，有，则；2.若，则；23.若对其常数ε0，有且对于某常数c1和所有充分大的正整数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)+n03对照(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)=θ(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)。最后举一个本方法对之无能为力的例子。考虑T(n)=2T(n/2)+nlogn对照(6.17)，我们有a=2，b=2，f(n)=nlogn，，虽然f(n)渐近地大于，但f(n)并不是多项式地大于，因为对于任意的正常数ε，，即f(n)在第二类情况与第三类情况的间隙里，本方法对它无能为力。递归方程组解的渐进阶的求法——差分方程法4这里只考虑形如：T(n)=c1T(n-1)+c2T(n-2)+…+ckT(n-k)+f(n)，n≥k(6.18)的递归方程。其中ci(i=l，2，…，k)为实常数，且ck≠0。它可改写为一个线性常系数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(t)=tk-c1tk-1-c2tk-2-…-ck=0(6.21)若t=r是(6.21)的m重实根，则得(6.20)的m个基础解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一对l重的共扼复根，则得(6.20)的2l个基础解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k个的基础解。而且，这k个基础解构成了(6.20)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到。但其中要用到(6.20)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦。因此在实际中，常常采用试探法，也就是根据f(n)的特点推测特解的形式，留下若干可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，将f(n)线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到f(n)相应的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的f(n)，给出(6.19)的相应特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常数。表6-1方程(6.19)的常用特解形式f(n)的形式条件方程(6.19)的特解的形式anC(a)≠0a是C(t)的m重根5nsC(1)≠01是C(t)的m重根nsanC(a)≠0a是C(t)的m重根第三步，写出(6.19)即(6.18)的通解(6.22)其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基础解系，g(n)是(6.19)的一个特解。然后由(6.18)的初始条件T(i)=Ti，i=1,2,…,k-1来确定(6.22)中的待定的组合常数{ai}，即依靠线性方程组或解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。第四步，估计(6.22)的渐近阶，即为所要求。下面用两个例子加以说明。例l考虑递归方程6它的相应特征方程为：C(t)=t2-t-1=0解之得两个单根和。相应的(6.20)的基础解系为{r0n，r1n}。相应的(6.19)的一个特解为F*(n)=-8，因而相应的(6.19)的通解为：F(n)=a0r0n+a1r1n-8令其满足初始条件，得二阶线性方程组：或或解之得，，从而于是。7例2考虑递归方程T(n)=4T(n-1)-4T(n-2)+2nn(6.23)和初始条件T(0)=0，T(1)=4/3。它对应的特征方程(6.21)为C(t)=t2-4t+4=0有一个两重根r=2。故相应的(6.20)的基础解系为{2n，2nn}。由于f(n)=2nn，利用表6-1，相应的(6.19)的一个特解为T*(n)=n2(p0+p1n)2n，代人(6.23)，定出p0=1/2，p1=1/6。因此相应的(6.19)的通解为：T(n)=a02n+a1n2n+n2(1/2+n/6)2n，令其满足初始条件得a0=a1=0，从而T(n)=n2(1/2+n/6)2n于是T(n)=θ(n32n)。递归方程组解的渐进阶的求法——母函数法关于T(n)的递归方程的解的母函数通常设为：(6.24)当(6.24)右端由于T(n)增长太快而仅在x=0处收敛时可另设(6.25)如果我们可以利用递归方程建立A(x)的一个定解方程并将其解出，那么，把A(x)展开成幂级数，则xn或xn/n!项的系数便是所求的递归方程的解。其渐近阶可接着进行估计。下面举两个例子加以说明。例1考虑线性变系数二阶齐次递归方程8(n-1)T(n)=(n-2)T(n-1)+2T(n-2)，n≥2(6.26)和初始条件T(0)=0，T(1)=1。根据初始条件及(6.26)，可计算T(2)=0，T(3)=T(1)=1。设{T(n)}的母函数为：由于T(0)=T(2)=0，T(1)=1，有：令B(x)=A(x)/x，即：那么：利用(6.26)并代入T(3)=1，得即两边同时沿[0,x]积分，并注意到B(0)=1，有：9把B(x)展开成幂级数，得从而最后得例2考虑线性变系数一阶非齐次递归方程D(n)=nD(n-1)+(-1)nn≥1(6.27)及初始条件D(0)=1很明显D(n)随n的增大而急剧增长。如果仍采用(6.24)形式的函数，则(6.24)的右端可能仅在x=0处收敛，所以这里的母函数设为：用xn/n!乘以(6.27)的两端，然后从1到∞求和得：10化简并用母函数表达，有：A(x)-1=xA(x)+e-x-1或(1-x)A(x)=e-x从而A(x)=e-x/(1-x)展成幂级数，则：故递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。111.代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。2.迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。3.套用公式法这个方法针对形如：T(n)=aT(n/b)+f(n)的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。4.差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。然后对得到的解作渐近阶的估计。5.母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。本章将逐一地介绍上述五种井法，并分别举例加以说明。本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。递归方程组解的渐进阶的求法——代入法用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。例如，我们要估计T(n)的上界