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

递推方程求解递推方程定义给定数列f(0),f(1),…,f(n),一个把f(n)和某些f(i)，0in，联系起来的等式称为递推方程给定关于f(n)的递推方程和初值，求f(n)称为解递推方程求解方法公式法换元法迭代归纳法差消法Master定理1.常系数线性齐次递推方程的求解（公式法）标准形式：k阶0,...,,,,0)()2()1()(2121kkkaaaaknknHanHanHanH是常数，求解步骤：（1）求出特征方程的k个根（2）如果没有重根，则该递推方程的通解为0...11kkkaxax待定常数knkknnCCCqCqCqCnH,...,,...)(212211如果有重根，如果q是e重特征根，通解对应于根q的部分为neeqnCnCC)...(121整个通解为各个不等的特征根的对应部分之和（3）代入初值确定待定常数。例6Fibonacci数列1,11021fffffnnn解：x2-x-1=0的根为251,251，递推方程的通解为nnnCCf25125121带入初值得125125112121CCCC解得25151,2515121CC112515125151nnnf例7H(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，通解为289314420212)1)(()(4321432143214142321CCCCCCCCCCCCCCCnCnCCnHnn解得92,0,31,974321CCCC解为nnnnnH292)1(31)1(97)(常系数线性非齐次递推方程求解（公式法）标准形121021)1(...,,)2(,)1(,)0()()(...)2()1()(kkdkHdHdHdHnfknHanHanHanH通解为对应的齐次通解加上特解特解的函数形式依赖于f(n)求解的关键是用待定系数法确定一个特解H*(n）)(*)()(nHnHnH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+P2(n-2)+P3]=3n2从而得到方程组12P1=3-34P1+12P2=029P1–17P2+12P3=0288115241741288115,2417,412*321nnaPPPn通解为288115241741)3()2(221nnCCannn例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(-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20120212aaaannn令,2nnab代入得bn=2bn-1+1，b0=4解得125,125nnnnab例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–n+13．叠代归纳法例13H(n)=(4n-6)H(n-1)H(1)=1)!1()!22(24)...42)(12()!22(2]13)...52)(32[(2)1(26)...104)(64(...)2()104)(64()1()64()(11nnnnnnnHnnnHnnnHnnHnn用归纳法验证4．差消法----化简递推方程例14求解递推方程0)1(2,1)(2)(11TnniTnnTni212112)1()1()(2)1()1()(2)(nininniTnTnnniTnnT相减并化简得22)1()1()(nnTnnnT由叠代得)()31...111(2)(2)1(...122121)(nOnnnOTnnnnnTT(n)=O(nlogn)nnnnnTnnT)1(212)1(1)(5.Master定理))(()(),()/(1,0),()(.3)log()(),()(.2)()(,0),()(1.)(),()/()()(1,1logloglogloglognfnTncfbnafncnnfnnnTnnfnnTnOnfnTnfbnaTnTnfbaaaaaabbbbb那么有和所有的充分大的且对于某个常数那么那么为非负整数为函数为常数，设例20nnTnT)3/(9)()()(),()(,,)(,3,9219log29log33nnTnOnfnnnnfba例211)3/2()(nTnT)log()(),()(,1,1)(,2/3,11log01log2/32/3nnTnnfnnnfba例22nnnTnTlog)4/(3)()log()(,4/3),(log)4/3()4/log()4/(3)/(,2.0),()(),(,log)(,4,33log793.03log44nnnTncncfnnnnbnafnnfnOnnnnfba充分大