求遞歸方程漸近界的常用方法(存儲版)
【正文】 =θ(n2)。其中ci (i=l，2，…，k)為實常數(shù)，且ck≠0。理論上，()的特解可以用Lagrange常數(shù)變易法得到。相應(yīng)的()的基礎(chǔ)解系為{r0n，r1n}。其漸近階可接著進行估計。如果仍采用()形式的函數(shù)，則()的右端可能僅在x=0處收斂，所以這里的母函數(shù)設(shè)為：用xn/n!乘以()的兩端，然后從1到∞求和得：化簡并用母函數(shù)表達(dá)，有：A(x) 1= xA(x)+ex1或(1x)A(x)=ex從而A(x)=ex/(1x)展成冪級數(shù)，則：故。因此相應(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)。下面用兩個例子加以說明。其中pi，i=1,2,…,s是待定常數(shù)。即()的任意一個解都可以表示成這k個基礎(chǔ)解的線性組合?？紤]T(n)=2T(n/2)+nlogn對照()，我們有a=2，b=2， f(n)=nlog n， ，雖然f(n)漸近地大于，但f(n)并不是多項式地大于，因為對于任意的正常數(shù)ε，即f(n)在第二類情況與第三類情況的間隙里，本方法對它無能為力。如果函數(shù)f(n)落在這兩個間隙之一中，或者雖有，但正規(guī)性條件不滿足，那么，本定理無能為力。定理直觀地告訴我們，遞歸方程解的漸近階由這兩個函數(shù)中的較大者決定。如果用T(n)表示規(guī)模為n的原問題的復(fù)雜性，用f(n)表示把原問題分成a個子問題和將a個子問題的解綜合為原問題的解所需要的時間，我們便有方程()。再舉一個例子。也就是將組成它的自由項n2留在原處，而將2個遞歸項T(n/2)分別攤給它的2個兒子結(jié)點。圖61 與方程()相應(yīng)的遞歸樹為了使迭代法的步驟直觀簡明、圖表化，我們引入遞歸樹。作為一個例子，考慮遞歸方程：接連迭代二次可將右端項展開為：由于對地板函數(shù)有恒等式：()式可化簡為：這仍然是一個遞歸方程，右端項還應(yīng)該繼續(xù)展開。把我們的推測代入遞歸方程，得到：我們不能由此推斷T(n)≤Cn，歸納法碰到障礙。在使用代入法時，有三點要提醒：(1)記號O不能濫用。進一步，數(shù)學(xué)歸納將證明此推測是正確的。因而得出結(jié)論：遞歸方程()的解的漸近階為O(nlogn)。 本來，遞歸方程都帶有初始條件，為了簡明起見，我們在下面的討論中略去這些初始條件。 3. 套用公式法 這個方法針對形如：T (n)=aT (n / b)+f (n) 的遞歸方程，給出三種情況下方程解的漸近階的三個相應(yīng)估計公式供套用。遞歸方程解的漸近階的求法遞歸算法在最壞情況下的時間復(fù)雜性漸近階的分析，都轉(zhuǎn)化為求相應(yīng)的一個遞歸方程的解的漸近階。 這個方法的基本步驟是通過反復(fù)迭代，將遞歸方程的右端變換成一個級數(shù)，然后求級數(shù)的和，再估計和的漸近階；或者，不求級數(shù)的和而直接估計級數(shù)的漸近階，從而達(dá)到對遞歸方程解的漸近階的估計。 本章將逐一地介紹上述五種方法，并分別舉例加以說明?？梢娢覀兊耐茰y是正確的。因此可以推測()與()有類似的上界T(n)=O(nlogn)。進一步的分析表明()對所有充分大的正整數(shù)n都成立，從而，遞歸方程()解的漸近階得到估計。我們要設(shè)法證明對于適當(dāng)選擇的正常數(shù)C和自然數(shù)n0，當(dāng)n≥n0時有T(n)≤Cn。方法的思想是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來達(dá)到對方程左端即方程的解的估計。這時若換用代入法，將可免去上述繁雜的代數(shù)運算。圖
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1