http://blog.csdn.net/explore_knight/archive/2007/09/17/1788046.aspx
這里只考慮形如：
T(n)=c1T(n-1)+c2T(n-2)+…+ ckT(n-k)+f(n)，n≥k (6.18)
的遞歸方程。其中ci (i=l，2，…，k)為實(shí)常數(shù)，且ck≠0。它可改寫(xiě)為一個(gè)線性常系數(shù)k階非齊次的差分方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=f(n)，n≥k (6.19)
(6.19)與線性常系數(shù)k階非齊次常微分方程的結(jié)構(gòu)十分相似，因而解法類同。限于篇幅，這里直接給出(6.19)的解法，略去其正確性的證明。
第一步，求(6.19)所對(duì)應(yīng)的齊次方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=0 (6.20)
的基本解系：寫(xiě)出(6.20)的特征方程：
C(t)=tk-c1tk-1-c2tk-2 -…-ck=0 (6.21)
若t=r是(6.21)的m重實(shí)根，則得(6.20)的m個(gè)基礎(chǔ)解rn，nrn，n2rn，…，nm-1rn；若ρeiθ和ρe-iθ是(6.21)的一對(duì)l重的共扼復(fù)根，則得(6.20)的2l個(gè)基礎(chǔ)解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出(6.21)的所有的根，就可以得到(6.20)的k個(gè)的基礎(chǔ)解。而且，這k個(gè)基礎(chǔ)解構(gòu)成了(6.20)的基礎(chǔ)解系。即(6.20)的任意一個(gè)解都可以表示成這k個(gè)基礎(chǔ)解的線性組合。
第二步，求(6.19)的一個(gè)特解。理論上，(6.19)的特解可以用Lagrange常數(shù)變易法得到。但其中要用到(6.20)的通解的顯式表達(dá)，即(6.20)的基礎(chǔ)解系的線性組合，十分麻煩。因此在實(shí)際中，常常采用試探法，也就是根據(jù)f(n)的特點(diǎn)推測(cè)特解的形式，留下若干可調(diào)的常數(shù)，將推測(cè)解代人(6.19)后確定。由于(6.19)的特殊性，可以利用迭加原理，將f(n)線性分解為若干個(gè)單項(xiàng)之和并求出各單項(xiàng)相應(yīng)的特解，然后迭加便得到f(n)相應(yīng)的特解。這使得試探法更為有效。為了方便，這里對(duì)三種特殊形式的f(n)，給出(6.19)的相應(yīng)特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常數(shù)。
表6-1 方程(6.19)的常用特解形式
f(n)的形式 條 件 方程(6.19)的特解的形式
{此處無(wú)法正常顯示，請(qǐng)看原文。}
第三步，寫(xiě)出(6.19)即(6.18)的通解
(6.22)
其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基礎(chǔ)解系，g(n)是(6.19)的一個(gè)特解。然后由(6.18)的初始條件
T(i)=Ti ，i=1,2,…,k-1
來(lái)確定(6.22)中的待定的組合常數(shù){ai}，即依靠線性方程組
或
解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。
第四步，估計(jì)(6.22)的漸近階，即為所要求。
下面用兩個(gè)例子加以說(shuō)明。
例l 考慮遞歸方程
它的相應(yīng)特征方程為：
C(t)=t2-t-1=0
解之得兩個(gè)單根和。相應(yīng)的(6.20)的基礎(chǔ)解系為{r0n，r1n}。相應(yīng)的(6.19)的一個(gè)特解為F*(n)=-8，因而相應(yīng)的(6.19)的通解為：
F(n)=a0r0n +a1r1n- 8
令其滿足初始條件，得二階線性方程組：
或
或
解之得，，從而
于是
。
例2 考慮遞歸方程
T(n)=4T(n-1)-4T(n-2)+2nn (6.23)
和初始條件T(0)=0，T(1)=4/3。
它對(duì)應(yīng)的特征方程(6.21)為
C(t)=t2-4t+4=0
有一個(gè)兩重根r =2。故相應(yīng)的(6.20)的基礎(chǔ)解系為{2n，2nn}。由于f(n)=2nn，利用表6-1，相應(yīng)的(6.19)的一個(gè)特解為
T*(n)=n2(p0+p1n)2n，
代人(6.23)，定出p0=1/2，p1=1/6。因此相應(yīng)的(6.19)的通解為：
T(n)=a02n+a1n2n+n2(1/2+n/6)2n，
令其滿足初始條件得a0=a1=0，從而
T(n)=n2(1/2+n/6)2n
于是T(n)=θ(n32n)。
本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/explore_knight/archive/2007/09/17/1788046.aspx