算法设计与分析-求解递归方程

《算法设计与分析-求解递归方程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递推方程求解递推方程定义给定数列f(0),f(1),…,f(n),一个把f(n)和某些f(i)，0i

2、n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4)=0H(0)=1,H(1)=0,H(2)=1,H(3)=2特征方程x4+x3-3x2-5x-2=0,特征根-1，-1，-1，2，通解为解得解为常系数线性非齐次递推方程求解（公式法）标准形通解为对应的齐次通解加上特解特解的函数形式依赖于f(n)求解的关键是用待定系数法确定一个特解H*(n）f(n)为n的t次多项式，一般H*(n)也为n的t次多项式例8求an+5an-1+6an-2=3n2的通解设an*=P1n2+P2n+P3,代入得P1n2+P2n+P3+5[P1(n-1)2+P2(n-1)+P3]+6[P1(n-2)2

3、+P2(n-2)+P3]=3n2从而得到方程组12P1=3-34P1+12P2=029P1–17P2+12P3=0通解为例10Hanoi塔H(n)=2H(n-1)+1设H*(n)=PP=2P+1,P=-1H(n)=A2n–1代入初值H(1)=1得A=1解为H(n)=2n–1f(n)为指数函数n，特解也为指数形式若不是特征根，则特解为H*(n)=Pn若是e重特征根，则特解为Pnen例13H(n)+5H(n-1)+6H(n-2)=424n令H*(n)=P4n,代入得P4n+5P4n-1+6P4n-2=424n42P=4216,P=16通解为H(n)=C1(-2)n+C2(

4、-3)n+4n+2H(n)–5H(n-1)+6H(n-2)=2n求特解2为1重根令H*(n)=Pn2n,代入得Pn2n–5P(n-1)2n-1+6P(n-2)2n-2=2n解得P=-2H*(n)=-n2n+12．转化成常系数线性递推方程求解---换元法例11令代入得bn=2bn-1+1，b0=4解得例12归并排序T(n)=2T(n/2)+n-1,n=2kT(2)=1H(k)=2H(k-1)+2k-1H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1,H*(k)=k2k+1通解H(k)=C2k+k2k+1,代入初值，得C=-1H(k)=-2k+k2k+1T(n)=nlogn

5、–n+13．叠代归纳法例13H(n)=(4n-6)H(n-1)H(1)=1用归纳法验证4．差消法----化简递推方程例14求解递推方程相减并化简得由叠代得T(n)=O(nlogn)5.Master定理例20例21例22