求遞歸方程漸近界的常用方法(文件)
【正文】 附加的“正規(guī)性”條件的直觀含義是a個子間題的再分解和再綜合所需要的時間最多與原問題的分解和綜合所需要的時間同階。如果函數(shù)f(n)落在這兩個間隙之一中，或者雖有，但正規(guī)性條件不滿足，那么，本定理無能為力。例3 考慮T(n)=3T(n/4)+nlogn對照()，我們有a=3，b=4， f(n)=nlog n， ，只要取，便有?？紤]T(n)=2T(n/2)+nlogn對照()，我們有a=2，b=2， f(n)=nlog n， ，雖然f(n)漸近地大于，但f(n)并不是多項式地大于，因為對于任意的正常數(shù)ε，即f(n)在第二類情況與第三類情況的間隙里，本方法對它無能為力。限于篇幅，這里直接給出()的解法，略去其正確性的證明。即()的任意一個解都可以表示成這k個基礎(chǔ)解的線性組合。因此在實際中，常常采用試探法，也就是根據(jù)f(n)的特點推測特解的形式，留下若干可調(diào)的常數(shù)，將推測解代人()后確定。其中pi，i=1,2,…,s是待定常數(shù)。 件 方程()的特解的形式 an C(a)≠0 a是C(t)的m重根 ns C(1)≠0 1是C(t)的m重根 nsan C(a)≠0 a是C(t)的m重根 第三步，寫出()即()的通解()其中{Ti(n)，i=0,1,2,…,n}是()的基礎(chǔ)解系，g(n)是()的一個特解。下面用兩個例子加以說明。例2 考慮遞歸方程 T(n)=4T(n1)4T(n2)+2nn ()和初始條件T(0)=0，T(1)=4/3。因此相應(yīng)的()的通解為：T(n)=a02n+a1n2n+n2(1/2+n/6)2n，令其滿足初始條件得a0=a1=0，從而T(n)=n2(1/2+n/6)2n于是T(n)=θ(n32n)。例1 考慮線性變系數(shù)二階齊次遞歸方程(n1)T(n)=(n2)T(n1)+2T(n2) ，n≥2 ()和初始條件T(0)=0，T(1)=1。如果仍采用()形式的函數(shù)，則()的右端可能僅在x=0處收斂，所以這里的母函數(shù)設(shè)為：用xn/n!乘以()的兩端，然后從1到∞求和得：化簡并用母函數(shù)表達，有：A(x) 1= xA(x)+ex1或(1x)A(x)=ex從而A(x)=ex/(1x)展成冪級數(shù)，則：故。設(shè){T(n)}的母函數(shù)為：由于T (0)=T (2)=0，T(1)= 1，有 ：令 B(x)= A (x)/x，即：那么：利用()并代入T (3)= 1，得即兩邊同時沿[0,x]積分，并注意到B(0)=1，有：把B(x)展開成冪級數(shù)，得從而最后得例2 考慮線性變系數(shù)一階非齊次遞歸方程D(n)=nD(n1)+(1)n其漸近階可接著進行估計。故相應(yīng)的()的基礎(chǔ)解系為{2n，2nn}。相應(yīng)的()的基礎(chǔ)解系為{r0n，r1n}。其中βj=Tjg(j)，j=0,1,2,…,k1。這使得試探法更為有效。理論上，()的特解可以用Lagrange常數(shù)變易法得到。如此，求出()的所有的根，就可以得到()的k個的基礎(chǔ)解。其中ci (i=l，2，…，k)為實常數(shù)，且ck≠0?？商子玫谌惽闆r的公式，得T(n)=θ(f(n))=θ(nlogn)。例1 考慮T(n)=9T(n/3)+n0對照()，我們有a=9，b=3， f(n)=n， ，取，便有，可套用第一類情況的公式，得T(n)=θ(n
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1