递归方程解的渐近阶的求法

《递归方程解的渐近阶的求法》由会员分享，可在线阅读，更多相关《递归方程解的渐近阶的求法（17页珍藏版）》请在装配图网上搜索。

1、目录囹递归方程组解的渐进阶的求法一代入法11囹递归方程组解的渐进阶的求法迭代法14度)递归方程组解的渐进阶的求法套用公式法17囹递归方程组解的渐进阶的求法差分方程法3囹递归方程组解的渐进阶的求法一母函数法7变递归方程解的渐近阶的求法递归方程组解的渐进阶的求法一套用公式法这个方法为估计形如：T(n)=aln/b)+f(n)(6.17)的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的由1和步1是常数，外加是一个确定的正函数。(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子问题的解的综合，

2、得到原问题的解。如果用丁(。)表示规模为n的原问题的复杂性，用*加表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。这个方法依据的是如下的定理：设a1和也1是常数f(c)是定义在非负整数上的一个确定的非负函数。又设了)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的加b可以是切,也可以是n/E那么，在*的三类情况下，我们有了)的渐近估计式：1.若对于某常数0,有/=0*期”)，则以同=9心为“).2 .若/二股喻口),则T=8(小即log.3 .若对其常数0,有且对于某常数C1和所有充分大的正整数。有翅n/b

3、)三如7),则T(n)=0(/(n)o这里省略定理的证明。在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉及的三类情况，都是拿人/?)与正以作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数一以”较大，则丁()=。俨鼠)：在第三类情况下,函数人加较大，则7V?)=0(fm)：在第二类情况下，两个函数一样大，则T(n)=G(ab即以”的对数作为因子乘上血)与丁)的同阶。此外，定理中的一些细节不能忽视。在第一类情况下加不仅必须比匕“女小，而且必须是多项式地比3氏”小，即/()必须渐近地小于3氏”

4、与一&的积，是一个正的常数：在第三类情况下,)不仅必须比4以”大，而且必须是多项式地比鼠”大，还要满足附加的正规性条件：af(n/b)cf(n)a这个附加的正规性”条件的直观含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数基本上都满足这个正规性条件。还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的在第一类情况和第二类情况之间有一个间隙：/(。)小于但不是多项式地小于匕“女”：类似地，在第二类情况和第三类情况之间也有一个间隙：加大于但不是多项式地大于鼠”。如果函数Kc)落在这两个间隙之一中，或者虽有,心)=

5、+6),但正规性条件不满足，那么，本定理无能为力。下面是几个应用例子。例1考虑T(n)=9T(n/3)+no对照(6.17),我们有a=9,b=3,f(n)=n,踊。二小)二取2门。，便有/6)二(力啊),可套用第一类情况的公式，得了()=6(加)。例2考虑T(n)=T(2n/3)+1对照(6.17),我们有a=1,b=3/2,f(n)=1,网“=2=1=,3),可套用第二类情况的公式，得T(n)=8(logn)例3考虑T(n)=3T(n/4)+nlognlo打c2lo33q793对照(6.17),我们有a=3,b=4,f(n)=nlogn,m“=()，只要取0.2,便有了=G(0f进一步，检

6、查正规性条件：33af(nfb)=3/(/4)=3(况/4)log(/4)=(log-log4)k(6.18)的递归方程。其中G(i=l,2,，k)为实常数，且CkNO。它可改写为一个线性常系数k阶非齐次的差分方程：T(n)-ci7n-1)-czT(n-2)-.-CkT(n-k)=/(n),nk(6.19)(6.19与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅,这里直接给出(6.19)的解法，略去其正确性的证明。第一步，求(6.19)所对应的齐次方程：T(n)-cT(n-1)-c2T(n-2)-.-CkT(n-k)=0(6.20)的基本解系：写出(6.20)的特征方程

7、：。(。匕阿-6产-心=o(6.21)若修是(6.21)的m重实根，则得(6.20)的m个基础解，,尸,n2/,，笠3；若pd。和pe的是(6.21)的一对/重的共扼复根,则得(6.20)的2/个基础解pncosnG,pnsinn0,npncosnO,npnsinn0,ncosnO,ncosnO.如此，求出(6.21)的所有的根，就可以得到(6.20)的A个的基础解。而且，这k个基础解构成了(6.20)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到。但其中要用到(6.20

8、)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦。因此在实际中，常常采用试探法，也就是根据)的特点推测特解的形式，留下若干可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，将线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到相应的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的人加，给出(6.19)的相应特解并列在表6-1中，可供直接套用。其中R,1=1,2，,S是待定常数。/()的形式表6-1方程(6.19)的常用特解形式a是C的m重根方程(6.19)的特解的形式C()对qi）知Pq+Pl.*+,+尸j,%1是C)的

9、ni重根伞。+1%+%.用2+汽成)哈产C3）对(外+巧,-+外2+外苏)以“。是C的m重根/（Pg+0我+巧+2第三步，写出(6.19)即(6.18)的通解七-13=0(6.22)其中7im),i=0,1,2,刀是(6.20)的基础解系,g(m是(6.19)的一个特解。然后由(6.18)的初始条件7(0=7i,i=1,2,.,k-1来确定(6.22)中的待定的组合常数加，即依靠线性方程组B-1窃力+冢力=%丁=012,为-11=0或2*(/)=%片121-11=0解出同,并代回(6.22)。其中向=不附,7=0,1,2，,k-1第四步，估计(6.22)的渐近阶，即为所要求。下而用两个例子加以

10、说明。例I考虑递归方程I2=0=s3=1+?(弘-1)+-2)w1它的相应特征方程为：c(r)=-M=o解之得两个单根生=(1一石和%=(14右)/2。相应的(6.20)的基础解系为仿n,k。相应的(6.19)的一个特解为尸(，)=-8,因而相应的(6.19)的通解为：F(n)=aofon+airin-8令其满足初始条件，得二阶线性方程组：“0+旬8=2即卬十时4-8=3或叼+。1=10(a。+(2)/2+(沏+。),6/2=11或(2q+(2C|=10沏+2(6.26)和初始条件7(0)=0,7(1)=1。根据初始条件及(626),可计算7(2)=0,T(3)=T(1)=1.设7)的母函数为

11、:二自7(瑜/n=0由于T(0)=7(2)=0711)=1,有：x)=郊+7(3)/+7(4)/+7/+=x(l+Z(3)x2+-(4)广+丁(盟)犬-1+)令B(x)=A(x)/x,即：5(x)=l+T(3)x2+7(4)?十+十那么:3。)=2r(3)彳+3(4)/+十5-1)附+出3=27X3*十34)/十十0-5川-1十8r-xBr(x)=2T(3)x+(37(4)-27(3)J+(47(5)-31(4)J+-+(-l)r(n)-(n-2)7(72-1)*+iBi利用(6.26)并代入T(3)=1,得8，(乃(1一元)=27x+27(2)7+27(3)1+2/伊一2)”一2+=2x(1

12、+7(3)x2+7(4)/+,+7(用/-1+,)=2汗R(X)%二二7十二B(卷 1-A两边同时沿0区积分,并注意到8(0)=1,有:In5(a)=-2x-21n(l-z)5(x)=一/(I-x)2把8(x)展开成基级数，得则=无耳讦冷=0=ok1?=*日广自j+1)N，=07=08 8=zz1=OJ=O(-/.u+l)8 K=s(sn=O i=O(-M2匚(+% n1) 工0AlAi从而 n&=2L72=0 2=0(_以.25+1)i !)0A1(6.27)及初始条件。(0)=1很明显0(。)随n的增大而急剧增长。如果仍采用(6.24)形式的函数，则(6.24)的右端可能仅在x=0处收敛，

13、所以这里的母函数设为：8=工/!n=0用YW?!乘以(6.27)的两端，然后从1到8求和得:5MZ口l淄/徐!=ZD(n一1)/(-1)!+Z(T)/引M=1=1W=1化简并用母函数表达，有：A(x)-1=X/4(x)+ex-1或(1-x)4(x)=ex从而A(x)=ex/(1-%)展成嘉级数,则:收=z(1，/泊工/J=0；=0=泛(-M!*/1=008(-1)/1)”=02=0=!(一坎”!上明!72=02=0故W3(甩)=加!y=o递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。递归方程的

14、形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法.1 .代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。2 .迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数,然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。3 .套用公式法这个方法针对形如:TSWaTS/bH/。?)的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。4 .差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的

15、方法来解递归方程。然后对得到的解作渐近阶的估计。5 .母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程,甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。本章将逐一地介绍上述五种井法，并分别举例加以说明。本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。立燧归方程组解的渐进阶的求法一代入法用这个办法既可估计上界也可估计下界。如前而所指出，方法的关键步骤在于预先对解答作出推测，然后用数

16、学归纳法证明推测的正确性。例如，我们要估计T(n)的上界，T(n)满足递归方程：7=2T(/2j)十题(6.1)其中1_是地板(floors)函数的记号，表示不大于n的最大整数。我们推测T(n)=O(rVogn),即推测存在正的常数C和自然数n。,使得当nNn。时有:T(n)Cnlogn(6.2)事实上，取Ho=22=4.并取C=max厚log砌十1那么,当now店2co时，(6.2)成立。今归纳假设当2牍展25o，那1时，(1.1.16)成立。那么，当的2腹皿时,我们有：7=2TQ/2j)+冏42。北鼠标:22)+同n0,(6.2)成立。可见我们的推测是正确的。因而得出结论:递归方程(6.1

17、)的解的渐近阶为O(nl0gn)o这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进行推测的高手。推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。我们在这里提三点建议：(1)如果一个递归方程类似于你从前见过的已知其解的方程，那么推测它有类似的解是合理的。作为例子，考虑递归方程：=2以|_/2_|十17)十题(6.3)右边项的变元中加了一个数17,使得方程看起来难于推测。但是它在形式上与(6.1)很类似。实际上，当n充分大时耿卬2十17)十”了。刈26相差无几。因此可以推测(6.3)与(6.1)有类似的上界T(n)=0(nlogn)o进一步，数学归纳将证明此推测是正确的。

18、(2)从较宽松的界开始推测，逐步逼近精确界。比如对于递归方程(6.1),要估计其解的渐近下界。由于明显地有了后。我们可以从推测丁(。)=。()开始，发现太松后，把推测的阶往上提，就可以得到7S)=Q(clog。)的精确估计。(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的已知其解的方程，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。例如考虑递归方程：T(M=2T(阔)+1。中(6.4)看起来很复杂，因为右端变元中带根号。但是，如果作变元替换m=logm即令皿2仞，将其代入(6.4),则(6.4)变成:T(2巧=27(_2M2_|)+掰(6.5)把m限

19、制在正偶数集上，则(6.5)又可改写为：T(2m)=2T(2m2)+m若令S(m)=T(2m),则S(m)满足的递归方程：S(m)=2S(m/2)+m,与(6.1)类似,因而有:S(m)=0(m1ogm),进而得到T(n)=T(2m)=S(m)=0(fn1ogm)=0(lognloglogn)(6.6)上面的论证只能表明：当(充分大的)。是2的正偶次塞或换句话说是4的正整数次耗时(6.6)才成立。进一步的分析表明(6.6)对所有充分大的正整数都成立，从而，递归方程(6.4)解的渐近阶得到估计。在使用代入法时，有三点要提醒：(1)记号。不能滥用。比如，在估计(6.1)解的上界时，有人可能会推测了

20、(/?)=。()，即对于充分大的。，有丁(。)与。7,其中。是确定的正的常数。他进一步运用数学归纳法，推出：T(n)=27(|_力/2)十用M2匕|_x/21+冷2C题/2十x=C题十题=(7+1)甩=0(刀)从而认为推测丁(。)=。(是正确的。实际上，这个推测是错误的，原因是他滥用了记号。，错误地把(C+I)与C”等同起来。(2)当对递归方程解的渐近阶的推测无可非议，但用数学归纳法去论证又通不过时，不妨在原有推测的基础上减去一个低阶项再试试。作为一个例子，考虑递归方程(同=?(历/2_|)十7(回/2)+1(6.7)其中是天花板(floors)函数的记号。我们推测解的渐近上界为O(n)o我们

21、要设法证明对于适当选择的正常数。和自然数%，当后外时有了修。把我们的推测代入递归方程，得到：(6.8)r()=cL/2j+c/2j+i=c(L/2j+L/2j)+i=c+i我们不能由此推断T(n)Cn,归纳法碰到障碍。原因在于(6.8)的右端比Cc多出一个低阶常量。为了抵消这一低阶量，我们可在原推测中减去一个待定的低阶量b,即修改原来的推测为T(n)0o囹递归方程组解的渐进阶的求法迭代法用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。作为一个例子

22、，考虑递归方程：=37(回/4)十同(6.9)接连迭代二次可将右端项展开为：=3T(甩/4+汽=+3(&/4j+3(w/4J/4J+37(皿制/4/4/46)(6,10)由于对地板函数有恒等式：|_|_园/alb=(6.(10) 化简为:丁=+3(,/4+3(，/42J+打加M*1)这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代/次后，将有T(ri)=应+3(n/4+3M/42卜3丁心/甲+,+3心/41+37(卜/4加J)(6.(11)而且当卜/4川_|=0(612)时，(6.11)不再是递归方程。这时：7=应+3(/4j+3(/42J+3(_M3J+.+3&/41+W)-)(6

23、J3)又因为awa,由(6.13)可得:7()?+3(?2/4+3(/42+3(/43+-+3(/4y+37(0)-)332333.442434，4%+3也7(。)(6.14)而由(6.12),知国og,从而3,十13邂4n+1=多晚？距晚4对二3/现43代人(6.14)得:了4+%10s尸.T0即方程(6的解7-(n)=0(n)o从这个例子可见迭代法导致繁杂的代数运算。但认真观察一下，要点在于确定达到初始条件的迭代次数和抓住每次迭代产生出来的“自由项(与7无关的项)遵循的规律。顺便指出，迭代法的前几步迭代的结果常常能启发我们给出递归方程解的渐近阶的正确推测。这时若换用代入法，将可免去上述繁杂

24、的代数运算。图6-1与方程(6.15)相应的递归树为了使迭代法的步骤直观简明、图表化，我们引入递归树，靠着递归树，人们可以很快地得到递归方程解的渐近阶。它对描述分治算法的递归方程特别有效。我们以递归方程丁(加=27(2)+标(6.15)为例加以说明。图6-1展示出(6.15)在迭代过程中递归树的演变。为了方便，我们假设“恰好是2的恭。在这里，递归树是一棵二叉树，因为(6.15)右端的递归项27(n/2)可看成T(n/2)+T(n/2)o图6-1(a)表示丁)集中在递归树的根处，(b)表示丁)已按(6.15)展开。也就是将组成它的自由项n2留在原处，而将2个递归项T(n/2)分别摊给它的2个儿子

25、结点。(c)表示迭代被执行一次。图6-1(d)展示出迭代的最终结果。图6-1中的每一棵递归树的所有结点的值之和都等于丁)。特别，已不含递归项的递归树(d)中所有结点的值之和亦然。我们的目的是估计这个和T(n)o我们看到有一个表格化的办法：先按横向求出每层结点的值之和，并记录在各相应层右端顶格处，然后从根到叶逐层地将顶格处的结果加起来便是我们要求的结果。照此，我们得到(6.15)解的渐近阶为取户)。再举一个例子。递归方程：T(n)=T(n/3)+T(2n/3)+n(6.16)的迭代过程相应的递归树如图6-2所示。其中，为了简明，再一次略去地板函数和天花板函数。总共0(nlon)图6-2迭代法解(6.16)的递归树当我们累计递归树各层的值时，得到每一层的和都等于。从根到叶的最长路径是设最长路径的长度为k,则应该有=log3/2于是TQi)冷=(k+1)=再(log3/2起+1)1=0即T(n)=0(nlogn)，以上两个例子表明，借助于递归树，迭代法变得十分简单易行。