算法設計中經(jīng)常會用到遞歸，利用遞歸式的方法可以清晰地顯示算法的整個過程，而對于分析算法的復雜度，解遞歸式就有了用處，這里的方法來自于《算法導論》。

（一）代換法：

實質(zhì)上就是數(shù)學歸納法，先對一個小的值做假設，然后推測更大的值得正確性。由于是數(shù)學歸納法，那么我們就需要對值進行猜測?，F(xiàn)在，我們看下面這個例子：

我們先假設一個結(jié)論T(n) = O(lg(n - b))，并且假設對T(n / 2上取整)成立（這就是數(shù)學歸納法了），那么把T(n / 2上取整)用假設的結(jié)論進行代換，我們有T(n) <= lg((n - b)) / 2上取整)

這是一個很簡單的例子，但是其中有些事情還是要交代的。

一個是結(jié)論的猜測不是一個容易的事情。另一個是在上面的例子中我沒有直接下結(jié)論說T(n) = O(lg(n))，而是減去了一個常數(shù)b，這是為什么呢？答案是：we can prove something stronger for a given value by assuming something?stronger for smaller values.還有一點值得說明，請看下面這個例子：

這里出現(xiàn)了sqrt(n)，我們采用變量代換的方法：令n = 2 ^ m,則上式變?yōu)門(2 ^ m) = 2T(2 ^ (m / 2) ),再設S(m) = T(2 ^ m)，則得到S(m) = 2S(m / 2) + 1。我們先假設S(m) = m - b

這里我們采用了變量代換的方法。如果假設時，感覺變量不明朗，那么這是一種很有效的方法。

（二）遞歸樹方法：

利用遞歸樹方法求算法復雜度我想最好的例子就是歸并排序了，這里我不想拿歸并排序做例子，而只是用書中一些更簡單形象的例子來說明：

根據(jù)上式我們建立遞歸式T(n) = 3T(n / 4) + cn^2，這里我們拋去上下界函數(shù)的影響（sloppiness that we can tolerate），并且把Theta(n ^ 2)用cn^2代替。下面建立遞歸樹模型：

在遞歸樹中，每一個結(jié)點都代表一個子代價，每層的代價是該層所有子代價的總和，總問題的代價就是所有層的代價總和。

所以，我們利用遞歸樹求解代價，需要知道什么呢，一個是每一層的代價，一個是層數(shù)，就是這兩個。

這些，都需要我們用覺察的態(tài)度來發(fā)現(xiàn)，而事實證明，這不是一件難事，很多情況下是有規(guī)律可循的。

我們且看上面這個例子，遞歸樹的構造很簡單，當遞歸調(diào)用到邊界是，就達到了常量T(1)，達到常量T(1)所用到的遞歸次數(shù)就是整個遞歸樹的深度，我們從圖中可以得到第i層的結(jié)點的代價為n / ( 4 ^ i )，當n / (4 ^ i) = 1即i = log4(n)時，遞歸到達了邊界，所以，整個遞歸樹的深度就是i = log4(n)。我們要求的總的代價是所有的總和，結(jié)果為O(n ^ 2)。計算過程我就不再累述了。但是，遞歸樹并不是都是這樣的滿的樹，也就是不是每一層的結(jié)點都是相同的結(jié)構，所以我們在構造遞歸樹的時候要仔細看好這一點，才能保證在計算時不會出錯。

（三）主方法：

其實應該叫做主定理方法，利用這個方法，我們只需要記住主定理的三種情況，并且在滿足一定的條件下，就可以速度解出遞歸式。主定理的三種情況不在這里給出，一定條件我只說一下我對于多項式大于(或小于)的理解，比如x和1.1x，那么x就是多項式小于1.1x，二者差了一個多項式(0.1x)，而至于x與xlgx就不存在多項式大于（或小于）的關系。

這個方法很直截了當，我在學習這個方法的時候其實就是從課后練習入主。但是三種情況，我卻無法牢記。