建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/10/143850.html#143880

因為《算法導論》第一部分1~5章的理論性太強，研究過多容易糾結，所以索性合起來快點講過去。

第四章：

這一章講的是遞歸式(recurrence)，遞歸式是一組等式或不等式，它所描述的函數是用在更小的輸入下該函數的值來定義的。

本章講了三種方法來解遞歸式，分別是代換法，遞歸樹方法，主方法。

1.代換法(Substitution method)(P38~P40)

定義：即在歸納假設時，用所猜測的值去代替函數的解。

用途：確定一個遞歸式的上界或下界。

缺點：只能用于解的形式很容易猜的情形。

總結：這種方法需要經驗的積累，可以通過轉換為先前見過的類似遞歸式來求解。

2.遞歸樹方法(Recursion-tree method)

起因：代換法有時很難得到一個正確的好的猜測值。

用途：畫出一個遞歸樹是一種得到好猜測的直接方法。

分析(重點)：在遞歸樹中，每一個結點都代表遞歸函數調用集合中一個子問題的代價。將遞歸樹中每一層內的代價相加得到一個每層代價的集合，再將每層的代價相加得到遞歸式所有層次的總代價。

總結：遞歸樹最適合用來產生好的猜測，然后用代換法加以驗證。

遞歸樹擴展過程：①.第二章2.3.2節分析分治法時圖2-5(P21~P22)的構造遞歸樹過程；②.第四章P41圖4-1的遞歸樹構造過程；這兩個圖需要好好分析。

3.主方法(Master method)

優點：針對形如T(n) = aT(n/b) + f(n)的遞歸式

缺點：并不能解所有形如上式的遞歸式的解。

具體分析：

T(n) = aT(n/b) + f(n)描述了將規模為n的問題劃分為a個子問題的算法的運行時間，每個子問題的規模為n/b。

在這里可以看到，分治法就相當于a=2, b=2, f(n) = O(n).

主方法依賴于主定理：(圖片點擊放大)

圖片可以不清晰，可以看書。

主定理的三種情況，經過分析，可以發現都是把f(n)與 比較。

第一種情況是 更大，第二種情況是 與f(n)相等，第三種情況是f(n)更大。

但是，這三種情況并未完全覆蓋所有可能的f(n)：

第一種情況是f(n)多項式的小于 ，而第三種情況是f(n)多項式的大于 ，即兩者相差的是 。如果兩者相差的不是 ，則無法用主定理來確定界。

比如算法導論P44最下面的 就不能用主定理來判斷。

至于主定理的證明，有興趣的可以拿筆在紙上推算，反正我這里是沒看的，畢竟時間有限，要選擇性的學習。

第五章：

本章是圍繞一個雇傭問題展開的。

問題：有一批參與面試的人，你要一個個面試(面試每個人都要花費c1)，如果當前面試者比自己的助理能力強，則辭掉當前助理的，并把當前面試者提拔為助理(雇傭一個人要花費c2)，一直面試完所有人。

這里考慮的是面試所花的money，假設總共有N人參加面試，有M人被雇傭過，則花費O(N*c1 + M*c2)，因為參與面試的人員順序是不確定的，所以要花費的money也是不確定的(N*c1是確定的，而M是不確定的，所以M*c2也是不確定的）。

首先介紹兩個概念：

1.概率分析：指在問題的分析中應用概率的技術。

2.隨機算法：如果一個算法的行為不只是由輸入決定，同時也由隨機數生成器所產生的數值決定，則成這個算法是隨機的。

書上講的理論性有點強，我這里用自己的話來說下：

首先說下概率分析，因為前面講到過：雇傭所需的花費與輸入序列有關，有N個面試人員(考慮每個人的能力不一樣)，則一共有N!中排列情況(即每種排列出現的概率是1/(N!))，于是假設每種排列花費Ti元，則所有供花費：

T1/(N!) + T2/(N!) + … + TN/(N!)。

其實這里可以結合高中學的正態分布來理解，都是講的每種情況出現的概率，思想差不多，所以這里也不需要什么概率論的知識，都是一些常識。

順便補充一下：5.2節的指示器隨機變量就是用的高中學的期望，用期望來表示概率。

再說下隨機算法，對于上面概率分析時的方法，雖然面試人員的排列是不確定的。但是如果當排列確定后，則所需花費也就確定了。而對于隨機算法，就算排列確定，其花費也是不確定的。即隨機發生在算法上，而不是發生在輸入分布上。這就是概率分析與隨機算法之間的區別。

比如按書上的，可以給每個人員隨機生成一個優先級，或者把每一個面試人員與其后的面試人員中隨機一員交換，來產生一個隨機的序列。

我以前總結過一些隨機算法，有興趣的朋友可以去看看：

1.《隨機化算法(1) — 隨機數》

2.《隨機化算法(2) — 數值概率算法》

3.《隨機化算法(3) — 舍伍德(Sherwood)算法》

4.《隨機化算法(4) — 拉斯維加斯(Las Vegas)算法》

5.《隨機化算法(5) — 蒙特卡羅(Monte Carlo)算法》

另外，比如像C/C++中庫函數rand()就是一個產生隨機變量的函數，但是它并不是真正意義上的隨機函數，所以稱之為偽隨機函數。因為當srand(seed)設置的seed一樣時，則rand()產生的隨機數也一樣，所以通常可以通過rand(-1)來把當前時間作為種子模擬隨機函數。

補充：在第五章的5.4節給出了幾個題目及其分析，這幾個題目都很有趣，不過對于數學也相對有一定的要求。其實可以很簡化的想：概率和期望是互相轉化的，這幾題就可以考慮是去求期望的。

我昨天在論壇出了一個邏輯面試題：一樓到十樓的每層電梯門口都放著一顆鉆石，鉆石大小不一。你乘坐電梯 從一樓到十樓，每層樓電梯門都會打開一次，只能拿一次鉆石，問怎樣才能拿到最大的一顆？

想必好多人都看過這題，網上的解答多種多項，我覺得此題應該考察的是最優解問題，按照最優解的思路，此題沒有100%的解決方法，只能盡量使其期望更高，也就是概率更大。這一題可以說是數學和哲學的完美結合，有點像人生，總想得到更多，但又怕后面的都不行，各種糾結啊。。。

總的來說，第五章說來說去都是一個期望的問題。