算法设计：第4讲――2013

绝大部分算法的执行，都表现为按某种条件重复地执行一些循环。而这些循环又经常可以用递归关系表达。因此，算法的运行时间也经常存在着一种递归关系。例如：求n！时间复杂度的分析递归算法的时间复杂度分析用生成函数求解递归方程用特征方程求解递归方程用递推法求解递归方程时间复杂度的分析用生成函数求解递归方程原理：递归算法的运行时间，随着递归深度的增加而增加。假定序列：a0,a1,…,ak表示递归算法在不同递归深度时的运行时间，则序列中每一个元素之间，存在着一定的递归关系。一般希望了解当递归深度k=n时，序列中元素an的值，即找出运行时间an与问题规模n的关系。用生成函数求解递归方程可以借助一个“参数”z来建立一个无穷级数的和：通过对G(z)的一系列演算，得到序列a0,a1,…,ak的一个通项表达式，便可容易地获得递归算法在递归深度k=n时的运行时间。kkkzazazaazG02210)(用生成函数求解递归方程定义：令是一个实数序列，构造如下的函数：则函数G(z)称为序列的生成函数。,,,210aaakkkzazazaazG02210)(,,,210aaa例如：函数则函数便是序列的生成函数用生成函数求解递归方程nnnnnnnxCxCxCCx2210)1(nx)1(nnnnnCCCC,,,,210生成函数的性质加法乘法z变换积分与微分用生成函数求解递归方程当c=1时：则函数便是序列1,1,1,…的生成函数用生成函数求解递归方程3322111zczczczc2111zzzz11如果对求导数，可得则函数便是序列1,2,3…的生成函数用生成函数求解递归方程如果对（2.2.7）式求导数，可得2111zzz022)1(321)1(1kkzkzzz2)1(1z如果对求积分，可得则函数便是序列的生成函数用生成函数求解递归方程如果对（2.2.7）式求导数，可得2111zzz1321312111lnkkzkzzzzz11ln,31,21,1举例1：汉诺塔(Hanoi)问题voidHanoi(chara,charb,charc,intn){if(n==1)printf(“%c-%c”,a,b);else{Hanoi(a,c,b,n-1);//将n-1个盘子a-cprintf(“%c-%c”,a,b);//将n从a到bHanoi(c,b,a,n-1);//将n-1个盘子b-c}}用生成函数求解递归方程如果对（2.2.7）式求导数，可得ba建立移动次数h(n)的递归方程，n代表盘数用生成函数求解递归方程1)1(1)1(2)(hnhnh构造生成函数：用h(n)作为系数，构造一个生成函数（n从1开始）用生成函数求解递归方程32)3()2()1()(xhxhxhxG1)(kkxkh根据递归方程，对G(x)进行变换，确定一个函数的幂级数展开式，令用生成函数求解递归方程3232)2(2)1(2)3()2()1()(2)(xhxhxhxhxhxGxxG32))2(2)3(())1(2)2(()1(xhhxhhxh用生成函数求解递归方程因为：h(n)=2h(n-1)+1,所以：h(n)-2h(n-1)=132)()21(xxxxGxxx1令用生成函数求解递归方程)21()1()(xBxAxG)21()1(2xxBxBAxA120BABA)21()1()(xxxxG求得：1,1BA所以用生成函数求解递归方程)1(1)21(1)(xxxG)1()2221(323322xxxxxx3322)12()12()12(xxxkkkx)12(112)(nnh，它是式中第n项的系数。当时n=64，移动次数为264-1。举例2：若某递归算法执行时间的递归表达式为：构造生成函数f(x)：对f(x)进行演算：用生成函数求解递归方程如果对（2.2.7）式求导数，可得1)2()1()2()1()(ffnfnfnf练习：用生成函数解下面的递归方程（1）f(n)=3f(n-1)+1f(1)=2（2）f(n)=5f(n-1)-6f(n-2)f(0)=1f(1)=0用生成函数求解递归方程如果对（2.2.7）式求导数，可得用特征方程解递归方程的两种情况K阶常系数线性齐次递归方程K阶常系数线性非齐次递归方程用特征方程求解递归方程如果对（2.2.7）式求导数，可得kibifknfanfanfanfik0)()()2()1()(21kibifngknfanfanfanfik0)()()()2()1()(21K阶常系数线性齐次递归方程用特征方程求解递归方程kibifknfanfanfanfik0)()()2()1()(21其中第2式是方程的初始条件，其中bi为常数。特征方程的建立可以求出特征方程的根，得到递归方程的通解。再利用递归方程的初始条件，确定通解中的待定系数，从而得到递归方程的解分成两种情况讨论1.是特征方程的k个互不相同的根。则递归方程的通解为：c1,c2,…,ck为待定系数，把递归方程的初始条件代入其中，建立联立方程，确定系数c1,c2,…,ck，从而可求出通解f(n)用特征方程求解递归方程kqqq,,,21nkknnqcqcqcnf2211)(2.特征方程的n个根中有r个重根则递归方程的通解为：c1,c2,…,ck为待定系数，把递归方程的初始条件代入其中，建立联立方程，确定系数c1,c2,…,ck，从而可求出通解f(n)用特征方程求解递归方程11,,,riiiqqqnkknirriiiniinqcqncnccqcqcnf)()(1111111例题1：三阶常系数线性齐次递归方程如下：用特征方程求解递归方程10)2(2)1(0)0()3(6)2(11)1(6)(fffnfnfnfnf＋－用特征方程求解该递归方程例题2：三阶常系数线性齐次递归方程如下：用特征方程求解递归方程用特征方程求解该递归方程7)2(2)1(1)0()3(3)2(7)1(5)(fffnfnfnfnf