求遞歸方程漸近界的常用方法-免費閱讀
【正文】 根據(jù)初始條件及()，可計算T(2)=0，T(3)=T(1)=1。它對應(yīng)的特征方程()為C(t)=t24t+4=0有一個兩重根r =2。然后由()的初始條件T(i)=Ti ，i=1,2,…,k1來確定()中的待定的組合常數(shù){ai}，即依靠線性方程組或解出{ai}，并代回()。由于()的特殊性，可以利用迭加原理，將f(n)線性分解為若干個單項之和并求出各單項相應(yīng)的特解，然后迭加便得到f(n)相應(yīng)的特解。第一步，求()所對應(yīng)的齊次方程：T(n)c1T(n1) c2T(n2)…ckT(nk)=0 ()的基本解系：寫出()的特征方程：C(t)=tkc1tk1c2tk2 …ck=0 ()若t=r是()的m重實根，則得()的m個基礎(chǔ)解rn，nrn，n2rn，…，nm1rn；若ρeiθ和ρeiθ是()的一對l重的共扼復(fù)根，則得()的2l個基礎(chǔ)解ρncosnθ，ρnsinnθ，nρncosnθ，nρnsinnθ，…，nl1ρncosnθ，nl1ρncosnθ。進一步，檢查正規(guī)性條件：只要取c=3/4，便有af(n/b)≤cf(n)，即正規(guī)性條件也滿足。我們在一般情況下將碰到的以多項式為界的函數(shù)基本上都滿足這個正規(guī)性條件。 這里省略定理的證明。遞歸方程組解的漸進階的求法——套用公式法這個方法為估計形如：T(n)=aT(n/b)+f(n) ()的遞歸方程解的漸近階提供三個可套用的公式。我們的目的是估計這個和T(n)。為了方便，我們假設(shè)n恰好是2的冪。但認真觀察一下，要點在于確定達到初始條件的迭代次數(shù)和抓住每次迭代產(chǎn)生出來的自由項(與T無關(guān)的項)遵循的規(guī)律。比如，我們推測()的解T(n)≤Cnlogn，而且已被證明是正確的，但是當n=l時，這個推測卻不成立，因為(Cnlogn)|n=1=0而T(l)0。作為一個例子，考慮遞歸方程其中是天花板(floors)函數(shù)的記號。例如考慮遞歸方程：看起來很復(fù)雜，因為右端變元中帶根號。但是它在形式上與()很類似。今歸納假設(shè)當2k1n0≤n≤2kn0 ，k≥1時，()成立。它不僅可以用來求解線性常系數(shù)高階齊次和非齊次的遞歸方程，而且可以用來求解線性變系數(shù)高階齊次和非齊次的遞歸方程，甚至可以用來求解非線性遞歸方程。那么，顯式解的漸近階即為所求。 遞歸方程的形式多種多樣，求其解的漸近階的方法也多種多樣。 有些遞歸方程可以看成一個差分方程，因而可以用解差分方程(初值問題)的方法來解遞歸方程。如前面所指出，方法的關(guān)鍵步驟在于預(yù)先對解答作出推測，然后用數(shù)學歸納法證明推測的正確性。推測遞歸方程的正確解，沒有一般的方法，得靠經(jīng)驗的積累和洞察力。比如對于遞歸方程()，要估計其解的漸近下界。他進一步運用數(shù)學歸納法，推出：從而認為推測T(n)=O(n)是正確的。為了抵消這一低階量，我們可在原推測中減去一個待定的低階量b，即修改原來的推測為T(n)≤Cnb 。這時：()又因為[a]≤a，由()可得：而由()，知i≤log4n ，從而，代人()得：即方程()的解它對描述分治算法的遞歸方程特別有效。圖61(d)展示出迭代的最終結(jié)果。其中，為了簡明，再一次略去地板函數(shù)和天花板函數(shù)。又設(shè)T(n)也是定義在非負整數(shù)上的一個非負函數(shù)，且滿足遞歸方程()。此外，定理中的一些細節(jié)不能忽視。例1 考慮T(n)=9T(n/3)+n0對照()，我們有a=9，b=3， f(n)=n， ，取，便有，可套用第一類情況的公式，得T(n)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1