求遞歸方程漸近界的常用方法(編輯修改稿)
2024-08-31 16:53 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 出()在迭代過(guò)程中遞歸樹的演變。為了方便，我們假設(shè)n恰好是2的冪。在這里，遞歸樹是一棵二叉樹，因?yàn)?)右端的遞歸項(xiàng)2T(n/2)可看成T(n/2)+T(n/2)。圖61(a)表示T(n)集中在遞歸樹的根處，(b)表示T(n)已按()展開。也就是將組成它的自由項(xiàng)n2留在原處，而將2個(gè)遞歸項(xiàng)T(n/2)分別攤給它的2個(gè)兒子結(jié)點(diǎn)。(c)表示迭代被執(zhí)行一次。圖61(d)展示出迭代的最終結(jié)果。圖61中的每一棵遞歸樹的所有結(jié)點(diǎn)的值之和都等于T(n)。特別，已不含遞歸項(xiàng)的遞歸樹(d)中所有結(jié)點(diǎn)的值之和亦然。我們的目的是估計(jì)這個(gè)和T(n)。我們看到有一個(gè)表格化的辦法：先按橫向求出每層結(jié)點(diǎn)的值之和，并記錄在各相應(yīng)層右端頂格處，然后從根到葉逐層地將頂格處的結(jié)果加起來(lái)便是我們要求的結(jié)果。照此，我們得到()解的漸近階為θ(n2)。再舉一個(gè)例子。遞歸方程：T(n)= T(n/3)+ T(2n/3)+n ()的迭代過(guò)程相應(yīng)的遞歸樹如圖62所示。其中，為了簡(jiǎn)明，再一次略去地板函數(shù)和天花板函數(shù)。圖62迭代法解()的遞歸樹當(dāng)我們累計(jì)遞歸樹各層的值時(shí)，得到每一層的和都等于n，從根到葉的最長(zhǎng)路徑是設(shè)最長(zhǎng)路徑的長(zhǎng)度為k，則應(yīng)該有，得，于是即T(n)=O(nlogn) 。以上兩個(gè)例子表明，借助于遞歸樹，迭代法變得十分簡(jiǎn)單易行。遞歸方程組解的漸進(jìn)階的求法——套用公式法這個(gè)方法為估計(jì)形如：T(n)=aT(n/b)+f(n) ()的遞歸方程解的漸近階提供三個(gè)可套用的公式。()中的a≥1和b≥1是常數(shù)，f (n)是一個(gè)確定的正函數(shù)。()是一類分治法的時(shí)間復(fù)雜性所滿足的遞歸關(guān)系，即一個(gè)規(guī)模為n的問(wèn)題被分成規(guī)模均為n/b的a個(gè)子間題，遞歸地求解這a個(gè)子問(wèn)題，然后通過(guò)對(duì)這a個(gè)子間題的解的綜合，得到原問(wèn)題的解。如果用T(n)表示規(guī)模為n的原問(wèn)題的復(fù)雜性，用f(n)表示把原問(wèn)題分成a個(gè)子問(wèn)題和將a個(gè)子問(wèn)題的解綜合為原問(wèn)題的解所需要的時(shí)間，我們便有方程()。這個(gè)方法依據(jù)的是如下的定理：設(shè)a≥1和b≥1是常數(shù)f (n)是定義在非負(fù)整數(shù)上的一個(gè)確定的非負(fù)函數(shù)。又設(shè)T(n)也是定義在非負(fù)整數(shù)上的一個(gè)非負(fù)函數(shù)，且滿足遞歸方程()。方程()中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三類情況下，我們有T(n)的漸近估計(jì)式：1. 若對(duì)于某常數(shù)ε0，有，則； 2. 若，則； 3. 若對(duì)其常數(shù)ε0，有且對(duì)于某常數(shù)c1和所有充分大的正整數(shù)n有af(n/b)≤cf(n)，則T(n)=θ(f(n))。 這里省略定理的證明。在應(yīng)用這個(gè)定理到一些實(shí)例之前，讓我們先指出定理的直觀含義，以幫助讀者理解這個(gè)定理。讀者可能已經(jīng)注意到，這里涉及的三類情況，都是拿f(n)與作比較。定理直觀地告訴我們，遞歸方程解的漸近階由這兩個(gè)函數(shù)中的較大者決定。在第一類情況下，函數(shù)較大，則T(n)=θ()；在第三類情況下，函數(shù)f(n)較大，則T(n)=θ(f (n))；在第二類情況下，兩個(gè)函數(shù)一樣大，則T(n)=θ()，即以n的對(duì)數(shù)作為因子乘上f(n)與T(n)的同階。此外，定理中的一些細(xì)節(jié)不能忽視。在第一類情況下f(n)不僅必須比小，而且必須是多項(xiàng)式地比小，即f(n)必須漸近地小于與的積，ε是一個(gè)正的常數(shù)；在第三類情況下f(n)不僅必須比大，而且必須是多項(xiàng)式地比大，還要滿足附加的“正規(guī)性”條件：af(n/b)≤cf(n)。這個(gè)附加的“正規(guī)性”條件的直觀含義是a個(gè)子間題的再分解和再綜合所需要的時(shí)間最多與原問(wèn)題的分解和綜合所需要的時(shí)間同階。我們?cè)谝话闱闆r
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1