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