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

因?yàn)椤端惴▽?dǎo)論》第一部分1~5章的理論性太強(qiáng)，研究過多容易糾結(jié)，所以索性合起來快點(diǎn)講過去。

第四章：

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

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

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

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

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

缺點(diǎn)：只能用于解的形式很容易猜的情形。

總結(jié)：這種方法需要經(jīng)驗(yàn)的積累，可以通過轉(zhuǎn)換為先前見過的類似遞歸式來求解。

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

起因：代換法有時(shí)很難得到一個(gè)正確的好的猜測值。

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

分析(重點(diǎn))：在遞歸樹中，每一個(gè)結(jié)點(diǎn)都代表遞歸函數(shù)調(diào)用集合中一個(gè)子問題的代價(jià)。將遞歸樹中每一層內(nèi)的代價(jià)相加得到一個(gè)每層代價(jià)的集合，再將每層的代價(jià)相加得到遞歸式所有層次的總代價(jià)。

總結(jié)：遞歸樹最適合用來產(chǎn)生好的猜測，然后用代換法加以驗(yàn)證。

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

3.主方法(Master method)

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

缺點(diǎn)：并不能解所有形如上式的遞歸式的解。

具體分析：

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

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

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

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

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

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

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

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

比如算法導(dǎo)論P(yáng)44最下面的 就不能用主定理來判斷。

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

第五章：

本章是圍繞一個(gè)雇傭問題展開的。

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

這里考慮的是面試所花的money，假設(shè)總共有N人參加面試，有M人被雇傭過，則花費(fèi)O(N*c1 + M*c2)，因?yàn)閰⑴c面試的人員順序是不確定的，所以要花費(fèi)的money也是不確定的(N*c1是確定的，而M是不確定的，所以M*c2也是不確定的）。

首先介紹兩個(gè)概念：

1.概率分析：指在問題的分析中應(yīng)用概率的技術(shù)。

2.隨機(jī)算法：如果一個(gè)算法的行為不只是由輸入決定，同時(shí)也由隨機(jī)數(shù)生成器所產(chǎn)生的數(shù)值決定，則成這個(gè)算法是隨機(jī)的。

書上講的理論性有點(diǎn)強(qiáng)，我這里用自己的話來說下：

首先說下概率分析，因?yàn)榍懊嬷v到過：雇傭所需的花費(fèi)與輸入序列有關(guān)，有N個(gè)面試人員(考慮每個(gè)人的能力不一樣)，則一共有N!中排列情況(即每種排列出現(xiàn)的概率是1/(N!))，于是假設(shè)每種排列花費(fèi)Ti元，則所有供花費(fèi)：

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

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

順便補(bǔ)充一下：5.2節(jié)的指示器隨機(jī)變量就是用的高中學(xué)的期望，用期望來表示概率。

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

比如按書上的，可以給每個(gè)人員隨機(jī)生成一個(gè)優(yōu)先級，或者把每一個(gè)面試人員與其后的面試人員中隨機(jī)一員交換，來產(chǎn)生一個(gè)隨機(jī)的序列。

我以前總結(jié)過一些隨機(jī)算法，有興趣的朋友可以去看看：

1.《隨機(jī)化算法(1) — 隨機(jī)數(shù)》

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

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

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

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

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

補(bǔ)充：在第五章的5.4節(jié)給出了幾個(gè)題目及其分析，這幾個(gè)題目都很有趣，不過對于數(shù)學(xué)也相對有一定的要求。其實(shí)可以很簡化的想：概率和期望是互相轉(zhuǎn)化的，這幾題就可以考慮是去求期望的。

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

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

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