算法设计与分析 第2版 第2章-递归算法设计技术.ppt

为求c1和c2，求解下面两个联立方程： f(0)=0=c1+c2，f(1)=1=c1( )+c2( ) 求得：c1= ，c2= 所以，f(n)= ≈ =O(φn)， 其中φ= 。 2. 非齐次递推式的求解 其通解形式如下： 　　f(n)=f(n)+f”(n) 其中，f’(n)是对应齐次递归方程的通解，f”(n)是原非齐次递归方程的特解。 常系数的线性非齐次递推式的一般格式如下： 　　现在还没有一种寻找特解的有效方法。一般是根据g(n)的形式来确定特解。 　　假设g(n)是n的m次多项式，即g(n)=c0nm+…+cm-1n+cm 则特解f”(n)=A0nm+A1nm-1+…+Am-1n+Am。 　　代入原递归方程求出A0、A1、…、Am。 　　再代入初始条件（f(i)=bi，0≤ik）求出系数得到最终通解。 有些情况下非齐次递推式的系数不一定是常系数。下面仅讨论几种简单且常用的非齐次递推式的求解过程。 其中g(n)是另一个序列。通过递推关系容易推出（2.8）的解是 f(n)=f(0)+ 例如，递推式f(n)=f(n-1)+1，且f(0)=0的解是f(n)=n。 通过递推关系推出（2.9）的解是 f(n)=g(n)g(n-1) … g(1)f(0) 例如，递推式f(n)=nf(n-1)，且f(0)=1的解是f(n)=n!。 （2）f(n)=g(n)f(n-1)（n≥1）且f(0)=1 （2.9） 其求解过程如下： f(n) = nf(n-1)+n!=n[(n-1)f(n-2)+(n-1)!]+n! = n(n-1)f(n-2)+2n! = n!(f(n-2)/(n-2)!+2) 构造一个辅助函数f(n)，令f(n)=n!f(n)，f(0)=f(0)=0，代入 (2.10)式有 n!f(n)=n(n-1)!f(n-1)+n! 简化为：f(n) = f(n-1)+1 它的解为：f(n) = f(0)+ = 0+n = n 因此，f(n) = n!f(n) = nn!。 （3）f(n)=nf(n-1)+n!（n≥1）且f(0)=0 （2.10） 【例2.14】求以下非齐次方程的解： f(n)=7f(n-1)-10f(n-2)+4n2 f(0)=1 f(1)=2 f(n)=7f(n-1)-10f(n-2)+4n2 f(0)=1 f(1)=2 　　解：对应的齐次方程为：f(n)=7f(n-1)-10f(n-2)，其特征方程为：x2-7x+10=0，求得其特征根为：q1=2，q2=5。所以对应的齐次递归方程的通解为f(n)=c12n+c25n。 　　由于g(n)=4n2，则令非齐式递归方程的特解为　　 　　f(n)=A0n2+A1n+A2 代入原递归方程，得： 　　A0n2+A1n+A2=7[A0(n-1)2+A1(n-1)+A2]-10[A0(n-2)2+A1(n-2)+A2]+4n2 　　化简后得到： 　　4A0n2+(-26A0+4A1)n+33A0-13A1+4A2=4n2 由此得到联立方程： 　　4A0=4 　　-26A0+4A1=0 　　33A0-13A1+4A2=0 求得：A0=1，A1=13/2，A2=103/8 所以非齐次递归方程的通解为： 　　f(n)=f(n)+f(n)=c12n+c25n+n2+13n/2+103/8 代入初始条件f(0)=1，f(1)=2，求得c1=-41/3，c2=43/24。 最后非齐次递归方程的通解为： 　　f(n)=-41/3×2n+43/24×5n+n2+13n/2+103/8。 2.5.2 递归树方法求解递归方程 　　用递归树求解递归方程的基本过程是： 　　（1）展开递归方程，构造对应的递归树。 　　（2）把每一层的时间进行求和，从而得到算法时间复杂度的估计。 【例2.15】分析以下递归方程的时间复杂度： T(n)=1 当n=1 T(n)=2T(n/2)+n2 当n1 　　解：构造的递归树如下图所示，当递归树展开时，子问题的规模逐步缩小，当到达递归出口时，即当子问题的规模为1时，递归树不再展开。 T(n)=1 当n=1 T(n)=2T(n/2)+n2 当n1 T(n)=2T(n/2)+n2=2[2T(n/4)+(n/2)2]+n2 =4T(n/4)+2(n/2)2+n2 　　显然在递归树中，第1层的问题规模为n，第2的层的问题规模为n/2，依此类推，当展开到第k+1层，其规模为n/2k=1，所以递归树的高度为log2n+1。 　　第1层有1个