求遞歸方程漸近界的常用方法(完整版)
【正文】 T(n)=O(nlog n)，即推測存在正的常數(shù)C和自然數(shù)n0，使得當(dāng)n≥n0時(shí)有：T(n)≤Cnlog n ()事實(shí)上，取n0=22=4，并取那么，當(dāng)n0≤n≤2n0時(shí)，()成立。作為例子，考慮遞歸方程：右邊項(xiàng)的變元中加了一個(gè)數(shù)17，使得方程看起來難于推測。(3)作變元的替換有時(shí)會使一個(gè)末知其解的遞歸方程變成類似于你曾見過的已知其解的方程，從而使得只要將變換后的方程的正確解的變元作逆變換，便可得到所需要的解。(2)當(dāng)對遞歸方程解的漸近階的推測無可非議，但用數(shù)學(xué)歸納法去論證又通不過時(shí)，不妨在原有推測的基礎(chǔ)上減去一個(gè)低階項(xiàng)再試試。(3)因?yàn)槲覀円烙?jì)的是遞歸方程解的漸近階，所以不必要求所作的推測對遞歸方程的初始條件（如T(0)、T(1)）成立，而只要對T(n)成立，其中n充分大。從這個(gè)例子可見迭代法導(dǎo)致繁雜的代數(shù)運(yùn)算。圖61展示出()在迭代過程中遞歸樹的演變。特別，已不含遞歸項(xiàng)的遞歸樹(d)中所有結(jié)點(diǎn)的值之和亦然。以上兩個(gè)例子表明，借助于遞歸樹，迭代法變得十分簡單易行。那么，在f(n)的三類情況下，我們有T(n)的漸近估計(jì)式：1. 若對于某常數(shù)ε0，有，則； 2. 若，則； 3. 若對其常數(shù)ε0，有且對于某常數(shù)c1和所有充分大的正整數(shù)n有af(n/b)≤cf(n)，則T(n)=θ(f(n))。這個(gè)附加的“正規(guī)性”條件的直觀含義是a個(gè)子間題的再分解和再綜合所需要的時(shí)間最多與原問題的分解和綜合所需要的時(shí)間同階。例3 考慮T(n)=3T(n/4)+nlogn對照()，我們有a=3，b=4， f(n)=nlog n， ，只要取，便有。限于篇幅，這里直接給出()的解法，略去其正確性的證明。因此在實(shí)際中，常常采用試探法，也就是根據(jù)f(n)的特點(diǎn)推測特解的形式，留下若干可調(diào)的常數(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)是()的一個(gè)特解。例2 考慮遞歸方程 T(n)=4T(n1)4T(n2)+2nn ()和初始條件T(0)=0，T(1)=4/3。例1 考慮線性變系數(shù)二階齊次遞歸方程(n1)T(n)=(n2)T(n1)+2T(n2) ，n≥2 ()和初始條件T(0)=0，T(1)=1。設(shè){T(n)}的母函數(shù)為：由于T (0)=T (2)=0，T(1)= 1，有 ：令 B(x)= A (x)/x，即：那么：利用()并代入T (3)= 1，得即兩邊同時(shí)沿[0,x]積分，并注意到B(0)=1，有：把B(x)展開成冪級數(shù)，得從而最后得例2 考慮線性變系數(shù)一階非齊次遞歸方程D(n)=nD(n1)+(1)n故相應(yīng)的()的基礎(chǔ)解系為{2n，2nn}。其中βj=Tjg(j)，j=0,1,2,…,k1。這使得試探法更為有效。如此，求出()的所有的根，就可以得到()的k個(gè)的基礎(chǔ)解?？商子玫谌惽闆r的公式，得T(n)=θ(f(n))=θ(nlogn)。還有一點(diǎn)很重要，即要認(rèn)識到上述三類情況并沒有覆蓋所有可能的f(n)。在應(yīng)用這個(gè)定理到一些實(shí)例之前，讓我們先指出定理的直觀含義，以幫助讀
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1