3、4.Mergesort(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遞推方程的實例:算法分析例2哪種排序算法在最壞情況下復雜度比較低？插入排序，歸并排序插入排序W(n)=W(n?1)+n?1W(1)=0解得W(n)=O(n2).歸并排序，不妨設n=2k.W(n)=2W(n/2)+n－1W(1)=0解得W(
4、n)=O(nlogn)513.2遞推方程的公式解法特征方程、特征根遞推方程的解與特征根的關系無重根下通解的結構求解實例有重根下通解的結構求解實例6其中a1,a2,…,ak為常數(shù)，ak?0稱為k階常系數(shù)線性齊次遞推方程b0,b1,…,bk?1為k個初值定義13.2常系數(shù)線性齊次遞推方程的標準形：常系數(shù)線性齊次遞推方程實例：Fibonacci數(shù)列的遞推方程7特征方程與特征根定義13.3特征方程xk?a1xk?1?…?ak=0，特征方程的根稱為遞推方程的特征根實例：遞推方程fn=fn?1+fn?2特征方程x2?x?1=0特征根8遞推方程解與特征根的關系定理13.1設q
5、是非零復數(shù)，則qn是遞推方程的解當且僅當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（因為q?0）?q是它的特征根定理13.2設h1(n)和h2(n)是遞推方程的解，c1,c2為任意常數(shù),則c1h1(n)+c2h2(n)也是這個遞推方程的解.推論若q1,q2,…,qk是遞推方程的特征根，則c1q1n+c2q2n+…+ckqkn是該遞推方程的解，其中c1,c2,…,ck是任意常數(shù).9無重根下通解的結構定義13.4
6、若對常系數(shù)線性齊次遞推方程的每個解h(n)都存在一組常數(shù)c1?,c2?,…,ck?使得h(n)=c1?q1n+c2?q2n+…+ck?qkn成立，則稱c1q1n+c2q2n+…+ckqkn為該遞推方程的通解定理13.3設q1,q2,…,qk是常系數(shù)線性齊次遞推方程不等的特征根，則H(n)=c1q1n+c2q2n+…+ckqkn為該遞推方程的通解.10例3Fibonacci數(shù)列：fn=fn?1+fn?2，特征根為通解為代入初值f0=1,f1=1,得解得解是實例11有重根下求解中的問題例4解特征方程x2?4x+4=0通解H(n)=c12n+c22n=c2n代入初值得
7、：c無解.問題：兩個解線性相關12有重根下的通解結構定理13.4設q1,q2,…,qt是遞推方程的不相等的特征根，且qi的重數(shù)為ei，i=1,2,…,t，令那么通解13例5求解以下遞推方程其中待定常數(shù)滿足以下方程組原方程的解為解特征方程x4+x3?3x2?5x?2=0,特征根?1,?1,?1,2通解為求解實例14遞推方程的標準型通解結構特解的求法多項式函數(shù)指數(shù)函數(shù)組合形式常系數(shù)線性非齊次遞推方程求解15證代入驗證,H(n)是解.下面證明任意解h(n)為某個齊次解與特解H*(n)之和.設h(n)為遞推方程的解，則h(n)?H*(n)是齊次解，即h(n)是一個齊次解
8、與H*(n)之和.定理1
