3、esort(A,q+1,r)5.Merge(A,p,q,r)//歸并排好序數(shù)組A[p..q]與A[q+1..r]插入排序算法INSERTION-SORT(A,n)1.forj?2tonkey?A[j]i?j–14whilei>0andA[i]>key5.doA[i+1]?A[i];i?i–17.A[i+1]?key4遞推方程的實(shí)例:算法分析例2哪種排序算法在最壞情況下復(fù)雜度比較低？插入排序，歸并排序插入排序W(n)=W(n?1)+n?1W(1)=0解得W(n)=O(n2).歸并排序，不妨設(shè)n=2k.W(n)=2W(n/2)+n－1W(1)=0解得W(n)=O(nlog
4、n)513.2遞推方程的公式解法特征方程、特征根遞推方程的解與特征根的關(guān)系無(wú)重根下通解的結(jié)構(gòu)求解實(shí)例有重根下通解的結(jié)構(gòu)求解實(shí)例6其中a1,a2,…,ak為常數(shù)，ak?0稱為k階常系數(shù)線性齊次遞推方程b0,b1,…,bk?1為k個(gè)初值定義13.2常系數(shù)線性齊次遞推方程的標(biāo)準(zhǔn)形：常系數(shù)線性齊次遞推方程實(shí)例：Fibonacci數(shù)列的遞推方程7特征方程與特征根定義13.3特征方程xk?a1xk?1?…?ak=0，特征方程的根稱為遞推方程的特征根實(shí)例：遞推方程fn=fn?1+fn?2特征方程x2?x?1=0特征根8遞推方程解與特征根的關(guān)系定理13.1設(shè)q是非零復(fù)數(shù)，則qn是遞推
5、方程的解當(dāng)且僅當(dāng)q是它的特征根.qn是遞推方程的解?qn?a1qn?1?a2qn?2?…?akqn?k=0?qn?k(qk?a1qk?1?a2qk?2?…?ak)=0?qk?a1qk?1?a2qk?2?…?ak=0（因?yàn)閝?0）?q是它的特征根定理13.2設(shè)h1(n)和h2(n)是遞推方程的解，c1,c2為任意常數(shù),則c1h1(n)+c2h2(n)也是這個(gè)遞推方程的解.推論若q1,q2,…,qk是遞推方程的特征根，則c1q1n+c2q2n+…+ckqkn是該遞推方程的解，其中c1,c2,…,ck是任意常數(shù).9無(wú)重根下通解的結(jié)構(gòu)定義13.4若對(duì)常系數(shù)線性齊次遞推方程的每
6、個(gè)解h(n)都存在一組常數(shù)c1?,c2?,…,ck?使得h(n)=c1?q1n+c2?q2n+…+ck?qkn成立，則稱c1q1n+c2q2n+…+ckqkn為該遞推方程的通解定理13.3設(shè)q1,q2,…,qk是常系數(shù)線性齊次遞推方程不等的特征根，則H(n)=c1q1n+c2q2n+…+ckqkn為該遞推方程的通解.10例3Fibonacci數(shù)列：fn=fn?1+fn?2，特征根為通解為代入初值f0=1,f1=1,得解得解是實(shí)例11有重根下求解中的問(wèn)題例4解特征方程x2?4x+4=0通解H(n)=c12n+c22n=c2n代入初值得：c無(wú)解.問(wèn)題：兩個(gè)解線性相關(guān)12有
7、重根下的通解結(jié)構(gòu)定理13.4設(shè)q1,q2,…,qt是遞推方程的不相等的特征根，且qi的重?cái)?shù)為ei，i=1,2,…,t，令那么通解13例5求解以下遞推方程其中待定常數(shù)滿足以下方程組原方程的解為解特征方程x4+x3?3x2?5x?2=0,特征根?1,?1,?1,2通解為求解實(shí)例14遞推方程的標(biāo)準(zhǔn)型通解結(jié)構(gòu)特解的求法多項(xiàng)式函數(shù)指數(shù)函數(shù)組合形式常系數(shù)線性非齊次遞推方程求解15證代入驗(yàn)證,H(n)是解.下面證明任意解h(n)為某個(gè)齊次解與特解H*(n)之和.設(shè)h(n)為遞推方程的解，則h(n)?H*(n)是齊次解，即h(n)是一個(gè)齊次解與H*(n)之和.定理1
