導論演算法

A. 演算法導論的介紹

《演算法導論》原書名——Introction to Algorithms，是2006年機械工業出版社出版出版的圖書，作者是Thomas H.Cormen、Charles E.Leiserson等。該書是一本十分經典的計算機演算法書籍，與高德納（Donald E.Knuth）的《計算機程序設計藝術》（The Art Of Computer Programming）相媲美。 《演算法導論》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作編著（其中Clifford Stein是第二版開始參與的合著者）。本書的最大特點就是將嚴謹性和全面性融入在了一起。

B. 《演算法導論》有什麼好的學習心得

本人沒有讀過這本書，文化水平不夠，就算讀了估計也是不知所雲，這個應該是比較專業的人看的吧，那我只能從網上摘錄些供大家分享。

推薦每學一個演算法，就去各個OJ（Online Judge）找一些相關題目做做，有時理論讓人很無語，分析代碼也是一個不錯的選擇。

C. 請教演算法導論這本書怎麼樣適合什麼程度的學習者

適合了解一門或以上編程語言的人，即使你沒學過數據結構也沒關系，因為它把數據結構中的演算法從基礎到非常深入全部都包括了，個人建議你先把C語言用熟悉了，然後再去看，演算法導論，如果有決心看完，數據結構都不用看，因為你看完演算法導論，就等於學會了非常高級的數據結構，但是看完很難。。。

至於C++，可以順帶著學一下，然後用C++自己把演算法實現一下，等於練兩倍。
也不一定非得學C++，可以學習Java或者C#，看你的發展方向

D. 《演算法導論》三種解遞歸式的方法

代入法可以用來確定一個遞歸式的上界或下界。這種方法很有效，但只能用於解的形式很容易猜的情形。

例如，我們需要確定下面遞歸式的上界：

該遞歸式與歸並排序相似，我們可以猜測其解為

代入法要求證明，恰當選擇常數 c>0，可有 T(n)≤cn lgn。首先假設此上界對所有正數 m<n 都成立，特別是對於 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。將其代入遞歸式，得到：

其中，只要 c≥1，最後一步都會成立。

並不存在通用的方法來猜測遞歸式的正確解，但總有一些試探法可以幫助做出好的猜測：

如果某個遞歸式與先前見過的類似，則可猜測該遞歸式有類似的解。如，遞歸式

看起來比較難解，因為右式 T 的自變數中加了 17，但我們可以猜測這個多出來的項對解的影響不大，因為當 n 很大時， 與 之間的差別並不大，兩者都將 n 分成均勻的兩半。

另一種方法是先證明遞歸式的較松的上下界，然後再縮小不確定性區間。例如，對遞歸式 ，因為遞歸式中有 n，而我們可以證明初始上界為 。然後，逐步降低其上界，提高其下界，直到達到正確的漸近確界 。

有時，我們或許能夠猜出遞歸式解的漸近界，但卻會在歸納證明時出現一些問題。通常，問題出在歸納假設不夠強，無法證明其准確的界，遇到這種情況時，可以去掉一個低階項來修改所猜測的界，以使證明順利進行。如下面的遞歸式：

可以猜測其解為 ，即要證明對適當選擇的 c，有 。有所猜測的界對遞歸式做替換，得到

由此無法得到 ，無論 c 的值如何。如果猜測一個更大的界，如 ，雖然這確實是上界，但事實上，所猜測的解 卻是正確的。為了證明這一點，要做一個更強的歸納假設。

從直覺上說，猜測 幾乎是正確的，只是差了一個常數 1，即一個低階項，然而，就因為差了一項，數學歸納法就無法證明出期望的結果。從所作的猜測中減去一個低階項，即 是個常數。現在有

只要 b≥ 1。這里，c 要選的足夠大，以便能處理邊界條件。

你可能會覺得從所作的猜測中減去一項有點兒與直覺不符。為什麼不是增加一項來解決問題呢？關鍵在於要理解我們是在用數學歸納法：通過對更小的值作更強的假設，就可以證明對某個給定值的更強的結論。

在運用漸近表示時很容易出錯。例如，對遞歸式 ，由假設 ，並證明

就是錯誤的，因為 c 是常數，因而錯誤地證明了 。錯誤在於沒有證明歸納假設的准確形式，即 。

有時，對一個陌生的遞歸式作一些簡單的代數變換，就會使之變成讀者較熟悉的形式。如下例子：

這個式子看上去比較難，但可以對它進行簡化，方法是改動變數。為了方便起見，不考慮數的截取整數問題，如將 化為整數。設 ，得

再設 ，得到新的遞歸式

這個式子看起來與 就非常像了，這個新的遞歸式的界是： 。將 帶回 ，有 。

有時候，畫出一個遞歸樹是一種得到好猜測的直接方法。在遞歸樹中，每一個節點都代表遞歸函數調用集合中一個子問題的代價。將樹中每一層內的代價相加得到一個每層代價的集合，再將每層的代價相加，得到的結果是所有層次的總代價。當用遞歸式表示分治演算法的運行時間時，遞歸樹的方法尤其有用。

遞歸樹最適合用來產生好的猜測，然後用代入法加以驗證。但使用遞歸樹產生好的猜測時，通常可以容忍小量的「不良量」，因為稍後就會證明所做的猜測。如果畫遞歸樹時非常地仔細，並且將代價都加了起來，那麼就可以直接用遞歸樹作為遞歸式的解的證明。

在講述例子之前，我們先來看一個幾何級數公式

對於實數 x≠1，式

是一個幾何級數（或稱指數級數），其值為

當和是無限的且 |x|<1 時，有無限遞減幾何級數

我們以遞歸式

為例來看一下如何用遞歸樹生成一個好的猜測。首先關注如何尋找解的一個上界，因為我們知道舍入對求解遞歸式通常沒有影響（此處即是我們需要忍受不精確的一個例子），因此可以為遞歸式

創建一顆遞歸樹，其中已將漸近符號改寫為隱含的常數系數 c>0。

構造的遞歸樹如下：

求所有層次的代價之和，確定整棵樹的代價：

最後的這個公式看起來不夠整潔，但我們可以再次充分利用一定程度的不精確，並利用無限遞減幾何級數作為上界。回退一步，得到：

此時，我們得到了遞歸式的一個猜測，在上面的例子里， 系數形成了一個遞減的等比級數，可知這些系數的總和的上界是常數 。由於樹根所需的代價為 ，所以根部的代價占總代價的一個常數部分。換句話說，整棵樹的總代價是由根部的代價所決定的。

事實上，如果 確實是此遞歸式的上界，那麼它一定是確界，為什麼呢？第一個遞歸調用所需要的代價是 ，所以 一定是此遞歸式的下界。

現在我們可以使用代換法來驗證猜測的正確性， 是遞歸式 的一個上界。只需要證明，當某常數 d>0， 成立。適用與前面相同的常數 c>0，有

只要 d≥ ，最後一步都會成立。

上圖是遞歸式

對應的遞歸樹。我們還是使用 c 來代表 項常數因子。當將遞歸樹內各層的數值加起來時，可以得到每一層的 cn 值。從根部到葉子的最長路徑是 。因為當 時， ，所以樹的深度是 。

直覺上，我們預期遞歸式的解至多是層數乘以每層的代價，也就是 。總代價被均勻地分布到遞歸樹內的每一層上。這里還有一個復雜點：我們還沒有考慮葉子的代價。如果這棵樹是高度為 的完整二叉樹，那麼有 個葉子節點。由於葉子代價是常數，因此所有葉子代價的總和為 ，或者說 。然而，這棵遞歸樹並不是完整的二叉樹，少於 個葉子，而且從樹根往下的過程中，越來越多的內部結點在消失。因此，並不是所有層次都剛好需要 cn 代價；越靠近底層，需要的代價越少。我們可以計算出准確的總代價，但記住我們只是想要找出一個猜測來使用到代入法中。讓我們容忍這些誤差，而來證明上界為 的猜測是正確的。

事實上，可以用代入法來證明 是遞歸式解的上界。下面證明 ，當 d 是一個合適的正值常數，則

上式成立的條件是 。因此，沒有必要去更准確地計算遞歸樹中的代價。

主方法給出了求解遞歸式的「食譜」方法，即將規模為 n 的問題劃分為 a 個子問題的演算法的運行時間，每個子問題規模為 ，a 和 b 是正常數。a 個子問題被分別遞歸地解決，時間各為 。劃分原問題和合並答案的代價由函數 描述。

從技術正確性角度來看，遞歸式實際上沒有得到很好的定義，因為 可能不是一個整數。但用 向上取整或向下取整來代替 a 項 並不影響遞歸式的漸近行為，因而，在寫分治演算法時略去向下取整和向上取整函數會帶給很大的方便。

其中我們將 n/b 解釋為 n 除以 b 的向下取整或向上取整。那麼 T(n) 有如下漸近界：

在使用主定理之前，我們需要花一點時間嘗試理解它的含義。對於三種情況的每一種，將函數 f(n) 與函數 進行比較。直覺上，兩個函數較大者決定了遞歸式的解。若函數 更大，如情況 1，則解為 T(n)= ( )。若函數 f(n) 更大，如情況 3，則解為 T(n)= (f(n))。若兩個函數大小相當，如情況 2，則乘上一個對數因子，解為 T(n)= ( )= ( )。

另外還有一些技術問題需要加以理解。在第一種情況下，不僅要有 小於 ，還必須是多項式地小於，也就是說， 必須漸近小於 ，要相差一個因子 ，其中 是大於 0 的常數。在第三種情況下，不是 大於 就夠了，而是要多項式意義上的大於，而且還要滿足「正則」條件 。

注意：三種情況並沒有覆蓋所有可能的 f(n)。當 f(n) 只是小於 但不是多項式地小於時，在第一種情況和第二種情況之間就存在一條「溝」。類似情況下，當 f(n) 大於 ，但不是多項式地大於時，第二種情況和第三種情況之間就會存在一條「溝」。如果 f(n) 落在任一條「溝」中，或是第三種情況種規則性條件不成立，則主方法就不能用於解遞歸式。

使用主方法很簡單，首先確定主定理的哪種情況成立，即可得到解。

例如：

對於這個遞歸式，我們有 a=9，b=3，f(n)=n，因此 = = 。由於 f(n) = ，其中 ， 因此可以應用於主定理的情況 1，從而得到解 T(n) = Θ( ) 。

現在考慮

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由於 f(n) = = Θ(1) ，因此可應用於情況2，從而得到解 T(n) = Θ( ) 。

對於遞歸式

我們有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由於 當 n，其中 ，因此，如果可以證明正則條件成立，即應用於情況 3。當 n 足夠大時，對於 ， ，因此，由情況 3，遞歸式的解為 T(n)= ( )。

主方法不能用於如下遞歸式：

雖然這個遞歸式看起來有恰當的形式：a=2，b=2， ，以及 。你可能錯誤地認為應該應用情況 3，因為 漸近大於 。問題出現在它並不是多項式意義上的大於。對任意正常數 ，比值 都漸近小於 。因此，遞歸式落入了情況 2 和情況 3 之間的間隙。

證明分為兩部分。第一部分分析「主」遞歸式 ，並作了簡化假設 僅定義在 b>1 的整數冪上，即 ， ， ，…。這部分從直覺上說明該定理為什麼是正確的。第二部分說明如何將分析擴展至對所有的正整數 n 都成立，主要是應用數學技巧來解決向下取整函數和向上取整函數的處理問題。

取正合冪時的證明

對於遞歸式

此時的假設是 n 為 b>1 的正合冪，且 b 不必是整數。分析可分成三個引理說明，第一個引理是將解原遞歸式的問題歸約為對一個含和式的求值的問題。第二個引理決定含和式的界，第三個引理把前兩個合在一起，證明當 n 為 b 的正合冪時主定理成立。

引理一 ：設 a≥1，b>1 為常數，f(n) 為定義在 b 的正合冪上的非負函數。定義 如下：

其中 i 是正整數，則有

證明：如下圖。根節點代價為 f(n)，它有 a 個子女，每個代價是 。（為方便起見可將 a 視為整數，但這對數學推導沒什麼影響。）每個子女又各有 a 個子女，代價為 。這樣就有 個結點離根的距離為 2。一般地，距根為 j 的結點有 個，每一個的代價為 。每一個葉結點的代價為 ，每一個都距根 ，因為 。樹中共有 個葉結點。

可以將樹中各層上的代價加起來而得到方程 ，第 j 層上內部結點的代價為 ，故各層內部結點的總代價和為

在其所基於的分治演算法中，這個和值表示了將問題分解成為子問題並將子問題的解合並時所花的代價，所有葉子的代價（即解 個規模為 1 的子問題的代價）為 。

根據遞歸樹，主定理的三種情況對應於樹中總代價的三種情況：1、由所有葉子節點的代價決定；2、均勻分布在各層上；3、由根結點的代價決定。

引理二 ：設 a≥1，b≥1 為常數， 為定義在 b 的整數冪上的非負函數。函數 由下式定義

對 b 的整數冪，該函數可被漸近限界為：

證明：對情況 1，有 ，這隱含著 。用它對方程 做代換，得

對 O 標記內的式子限界，方法是提出不變項並作簡化，得到一個上升幾何級數：

因為 b 與 都是常數，最後的表達式可化簡為 。用此表達式對 作替換，得

情況 1 得以驗證。

為證情況 2，假設 ，有 。用此式對方程 作替換，得

對 記號中的式子做類似情況 1 中的限界，但所得並非是幾何級數，而是每項都是相同的:

用此方程對 中的和式做替換，有

則情況 2 得以驗證。情況 3 也可以用類似的方式證明。

引理三 ：設 a≥1，b>1 是常量， 是定義在 b 的整數冪上的非負函數。定義 T(n) 如下：

其中 i 是正整數。對於 b 的整數冪，T(n) 可有如下漸近界：

證明：用引理二給出的界來對引理一中的式 求值。對情況 1 有

對情況 2 有

對情況 3 有

E. 演算法導論的內容簡介

《演算法導論》自第一版出版以來，已經成為世界范圍內廣泛使用的大學教材和專業人員的標准參考手冊。本書全面論述了演算法的內容，從一定深度上涵蓋了演算法的諸多方面，同時其講授和分析方法又兼顧了各個層次讀者的接受能力。各章內容自成體系，可作為獨立單元學習。所有演算法都用英文和偽碼描述，使具備初步編程經驗的人也可讀懂。全書講解通俗易懂，且不失深度和數學上的嚴謹性。第二版增加了新的章節，如演算法作用、概率分析與隨機演算法、線性編程等，幾乎對第一版的各個部分都作了大量修訂。
本書深入淺出，全面地介紹了計算機演算法。對每一個演算法的分析既易於理解又十分有趣，並保持了數學嚴謹性。本書的設計目標全面，適用於多種用途。涵蓋的內容有：演算法在計算中的作用，概率分析和隨機演算法的介紹。本書專門討論了線性規劃，介紹了動態規劃的兩個應用，隨機化和線性規劃技術的近似演算法等，還有有關遞歸求解、快速排序中用到的劃分方法與期望線性時間順序統計演算法，以及對貪心演算法元素的討論。本書還介紹了對強連通子圖演算法正確性的證明，對哈密頓迴路和子集求和問題的NP完全性的證明等內容。全書提供了900多個練習題和思考題以及敘述較為詳細的實例研究。
本書內容豐富，對本科生的數據結構課程和研究生的演算法課程都是很實用的教材。本書在讀者的職業生涯中，也是一本案頭的數學參考書或工程實踐手冊。