遞歸方程組解的漸進階的求法——代入法

遞歸方程組解的漸進階的求法——代入法

用這個辦法既可估計上界也可估計下界。如前面所指出，方法的關鍵步驟在于預先對解答作出推測，然后用數學歸納法證明推測的正確性。

例如，我們要估計T(n)的上界，T(n)滿足遞歸方程：

其中是地板(floors)函數的記號，表示不大于n的最大整數。

我們推測T(n)=O(nlog n)，即推測存在正的常數C和自然數n₀，使得當n≥n₀時有：

T(n)≤Cnlog n (6.2)

事實上，取n₀=2²=4，并取

那么，當n₀≤n≤2n₀時，(6.2)成立。今歸納假設當2^k-1n₀≤n≤2^kn₀ ，k≥1時，(1.1.16)成立。那么，當2^kn₀≤n≤2^k+1n₀時，我們有：

即(6.2)仍然成立，于是對所有n≥n₀，(6.2)成立。可見我們的推測是正確的。因而得出結論：遞歸方程(6.1)的解的漸近階為O(nlogn)。

這個方法的局限性在于它只適合容易推測出答案的遞歸方程或善于進行推測的高手。推測遞歸方程的正確解，沒有一般的方法，得靠經驗的積累和洞察力。我們在這里提三點建議：

(1) 如果一個遞歸方程類似于你從前見過的已知其解的方程，那么推測它有類似的解是合理的。作為例子，考慮遞歸方程：

右邊項的變元中加了一個數17，使得方程看起來難于推測。但是它在形式上與(6.1)很類似。實際上，當n充分大時

與

相差無幾。因此可以推測(6.3)與(6.1)有類似的上界T(n)=O(nlogn)。進一步，數學歸納將證明此推測是正確的。

(2)從較寬松的界開始推測，逐步逼近精確界。比如對于遞歸方程(6.1)，要估計其解的漸近下界。由于明顯地有T(n)≥n，我們可以從推測T(n)=Ω(n)開始，發現太松后，把推測的階往上提，就可以得到T(n)=Ω(nlog n)的精確估計。

(3)作變元的替換有時會使一個末知其解的遞歸方程變成類似于你曾見過的已知其解的方程，從而使得只要將變換后的方程的正確解的變元作逆變換，便可得到所需要的解。例如考慮遞歸方程：

看起來很復雜，因為右端變元中帶根號。但是，如果作變元替換m=logn，即令n=2^m，將其代入(6.4)，則(6.4)變成：

把m限制在正偶數集上，則(6.5)又可改寫為：

T(2^m)=2T(2^m/2)+m

若令S(m)=T(2^m)，則S(m)滿足的遞歸方程：

S(m)=2S(m/2)+m ，

與(6.1)類似，因而有：

S(m)=O(m1og m)，

進而得到T(n)=T(2^m)=S(m)=O(m1ogm)=O(lognloglogn) (6.6)

上面的論證只能表明：當(充分大的)n是2的正偶次冪或換句話說是4的正整數次冪時(6.6)才成立。進一步的分析表明(6.6)對所有充分大的正整數n都成立，從而，遞歸方程(6.4)解的漸近階得到估計。

在使用代入法時，有三點要提醒：

(1)記號O不能濫用。比如，在估計(6.1)解的上界時，有人可能會推測T(n)=O(n)，即對于充分大的n，有T(n)≤Cn ，其中C是確定的正的常數。他進一步運用數學歸納法，推出：

從而認為推測T(n)=O(n)是正確的。實際上，這個推測是錯誤的，原因是他濫用了記號O ，錯誤地把(C+l)n與Cn等同起來。

(2)當對遞歸方程解的漸近階的推測無可非議，但用數學歸納法去論證又通不過時，不妨在原有推測的基礎上減去一個低階項再試試。作為一個例子，考慮遞歸方程

其中是天花板(floors)函數的記號。我們推測解的漸近上界為O(n)。我們要設法證明對于適當選擇的正常數C和自然數n₀，當n≥n₀時有T(n)≤Cn。把我們的推測代入遞歸方程，得到：

我們不能由此推斷T(n)≤Cn，歸納法碰到障礙。原因在于(6.8)的右端比Cn多出一個低階常量。為了抵消這一低階量，我們可在原推測中減去一個待定的低階量b，即修改原來的推測為T(n)≤Cn-b 。現在將它代人(6.7)，得到：

只要b≥1，新的推測在歸納法中將得到通過。

(3)因為我們要估計的是遞歸方程解的漸近階，所以不必要求所作的推測對遞歸方程的初始條件（如T(0)、T(1)）成立，而只要對T(n)成立，其中n充分大。比如，我們推測(6.1)的解T(n)≤Cnlogn，而且已被證明是正確的，但是當n=l時，這個推測卻不成立，因為(Cnlogn)|_n=1=0而T(l)>0。