求遞歸方程漸近界的常用方法-文庫吧
2025-07-20 16:53 本頁面
【正文】 是，如果作變元替換m=logn，即令n=2m ，將其代入()，則()變成：把m限制在正偶數(shù)集上，則()又可改寫為：T(2m)=2T(2m/2)+m若令S(m)=T(2m)，則S(m)滿足的遞歸方程：S(m)=2S(m/2)+m ，與()類似，因而有：S(m)=O(m1og m)，進(jìn)而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn) ()上面的論證只能表明：當(dāng)(充分大的)n是2的正偶次冪或換句話說是4的正整數(shù)次冪時()才成立。進(jìn)一步的分析表明()對所有充分大的正整數(shù)n都成立，從而，遞歸方程()解的漸近階得到估計。在使用代入法時，有三點(diǎn)要提醒：(1)記號O不能濫用。比如，在估計()解的上界時，有人可能會推測T(n)=O(n)，即對于充分大的n，有T(n)≤Cn ，其中C是確定的正的常數(shù)。他進(jìn)一步運(yùn)用數(shù)學(xué)歸納法，推出：從而認(rèn)為推測T(n)=O(n)是正確的。實際上，這個推測是錯誤的，原因是他濫用了記號O ，錯誤地把(C+l)n與Cn等同起來。(2)當(dāng)對遞歸方程解的漸近階的推測無可非議，但用數(shù)學(xué)歸納法去論證又通不過時，不妨在原有推測的基礎(chǔ)上減去一個低階項再試試。作為一個例子，考慮遞歸方程其中是天花板(floors)函數(shù)的記號。我們推測解的漸近上界為O(n)。我們要設(shè)法證明對于適當(dāng)選擇的正常數(shù)C和自然數(shù)n0，當(dāng)n≥n0時有T(n)≤Cn。把我們的推測代入遞歸方程，得到：我們不能由此推斷T(n)≤Cn，歸納法碰到障礙。原因在于()的右端比Cn多出一個低階常量。為了抵消這一低階量，我們可在原推測中減去一個待定的低階量b，即修改原來的推測為T(n)≤Cnb ?，F(xiàn)在將它代人()，得到：只要b≥1，新的推測在歸納法中將得到通過。(3)因為我們要估計的是遞歸方程解的漸近階，所以不必要求所作的推測對遞歸方程的初始條件（如T(0)、T(1)）成立，而只要對T(n)成立，其中n充分大。比如，我們推測()的解T(n)≤Cnlogn，而且已被證明是正確的，但是當(dāng)n=l時，這個推測卻不成立，因為(Cnlogn)|n=1=0而T(l)0。遞歸方程組解的漸進(jìn)階的求法——迭代法用這個方法估計遞歸方程解的漸近階不要求推測解的漸近表達(dá)式，但要求較多的代數(shù)運(yùn)算。方法的思想是迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來達(dá)到對方程左端即方程的解的估計。作為一個例子，考慮遞歸方程：接連迭代二次可將右端項展開為：由于對地板函數(shù)有恒等式：()式可化簡為：這仍然是一個遞歸方程，右端項還應(yīng)該繼續(xù)展開。容易看出，迭代 i 次后，將有（）而且當(dāng)時，()不再是遞歸方程。這時：()又因為[a]≤a，由()可得：而由()，知i≤log4n ，從而，代人()得：即方程()的解 T(n)=O(n)。從這個例子可見迭代法導(dǎo)致繁雜的代數(shù)運(yùn)算。但認(rèn)真觀察一下，要點(diǎn)在于確定達(dá)到初始條件的迭代次數(shù)和抓住每次迭代產(chǎn)生出來的自由項(與T無關(guān)的項)遵循的規(guī)律。順便指出，迭代法的前幾步迭代的結(jié)果常常能啟發(fā)我們給出遞歸方程解的漸近階的正確推測。這時若換用代入法，將可免去上述繁雜的代數(shù)運(yùn)算。圖61 與方程()相應(yīng)的遞歸樹為了使迭代法的步驟直觀簡明、圖表化，我們引入遞歸樹。靠著遞歸樹，人們可以很快地得到遞歸方程解的漸近階。它對描述分治算法的遞歸方程特別有效。我們以遞歸方程T(n)=2T(n/2)+n2 ()為例加以說明。圖61展示
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1