算法設計與分析基礎(第3版‧詳解版‧附雙色版習題詳解手冊)（簡體書）

作者基於豐富的教學經驗，開發了一套全新的算法分類方法。該分類法站在通用問題求解策略的高度，對現有大多數算法進行了較為準確的分類，旨在引領讀者沿著清晰、一致、連貫的思路來探索算法的設計與分析。
《算法設計與分析基礎（第3版 詳解版）》適合用作算法設計與分析的基礎教材，也適合任何有興趣探究算法奧秘的讀者自學使用。

阿納尼·樂維汀(Anany Levitin)博士
早年畢業於莫斯科國立大學，先後獲得數學碩士和博士學位。他還擁有以色列耶路撒冷希伯來大學數學學士學位和美國肯塔基大學計算機科學碩士學位。在維拉諾瓦大學數學系和計算機科學系任教近40年後，他以該校榮休教授身份退休。20世紀90 年代初，他為AT&T貝爾實驗室擔任過顧問。《算法設計與分析基礎》被翻譯成五種語言，被全球好幾百所大學用作教材。
樂維汀博士具有數學家特有的一本正經的幽默，因而深受同事和學生的喜愛。業余時間除了拼圖，他還喜歡與自己的小外孫打乒乓球，與妻子一起外出散步。

云鶴
斜槓型手藝人，喜歡下廚房的資深程序員，左腦發達，篤信過程決定結果，細節決定成敗。做事情重視基操，講究三思而後行。業余時間寫過幾個小程序來解決一些實際問題。

作者基於豐富的教學經驗，開發了一套全新的算法分類方法。該分類法站在通用問題求解策略的高度，對現有大多數算法準確分類，從而引領讀者沿著一條清晰、一致、連貫的思路來探索算法設計與分析這一迷人領域。《算法設計與分析基礎（第3版 詳解版）》作為第3版，相對前版調整了多個章節的內容和順序，同時增加了一些算法，並擴展了算法的應用，使得具體算法和通用算法設計技術的對應更加清晰有序；各章累計增加了70道習題，其中包括一些有趣的謎題和面試問題。
《算法設計與分析基礎（第3版 詳解版）》十分適合用作算法設計和分析的基礎教材，也適合任何有興趣探究算法奧秘的讀者使用，只要讀者具備數據結構和離散數學的知識即可。

一個人在接受科技教育時，最有價值的收獲是能使其終身受益的通用智能工具。
——喬治•福賽斯
（譯注：原文為The most valuable acquisitions in a scientific or technical education are the general-purpose mental tools which remain serviceable for a life-time，出自1968年發表的What to do till the computer scientist comes。福賽斯(George Forsythe，1917—1972)1939年在布朗大學獲得博士學位，二戰後供職於斯坦福大學數學系，後來在該校創辦計算機系。他先後培養的博士生超過190名。他與MATLAB之父莫勒合著的《線性代數系統的計算機求解》出版於1967年。）

算法在計算科學和計算實踐中發揮著核心作用。基於這樣的認知，涌現出大量相關的著述，尤其是教材。它們在介紹算法時基本上選擇遵循兩種方案。一種是根據問題類型對算法進行分類。這樣的書用單獨的章節介紹排序、查找以及圖等算法。這種方案的優點在於，能立即對比同一問題場景下不同算法的效率。缺點在於，它強調的是問題類型，忽略了算法設計技術。
第二種方案是圍繞算法設計技術進行組織。採用這種組織方式，如果來自不同計算領域的算法採用的是相同的設計方法，就把它們歸為一組。我和許多人一樣(例如[BaY95])，認為這種組織方式更適合算法設計與分析基礎課程。強調算法設計技術主要有三個原因。第一，這些技術為學生提供了工具來為新的問題設計算法。這使學習算法設計技術具有實踐意義上的價值。第二，它們根據基本的設計理念來對眾多已知的算法進行分類。尋找不同應用領域的算法之間的共性，這應該是計算機科學教育的一個主要目標。畢竟，每一門學科都將其主要課題的分類視為其學科的要點甚至是中心點。第三，在我看來，算法設計技術作為一般的問題解決策略具有實用性，適用於計算以外的問題。
遺憾的是，無論從理論還是教育的角度，算法設計技術的傳統分類法都有幾個重大的缺陷。最重要的是沒有對許多重要的算法進行分類。這一不足迫使其他教科書的作者背離設計技術的組織形式，在書中加入相應的章節來處理具體的問題類型。這樣的轉換導致算法課程喪失連貫性，注定會導致學生覺得亂。
算法設計技術的新分類法
傳統算法設計技術分類法的缺陷讓人感到失望，所以我開發了一套新的分類法[Lev99]，這也是本書的基礎。新的分類法主要有下面幾個優點。
新的分類法比傳統分類法更全面。新加入的蠻力法、減治法、變治法、時空權衡和迭代改進等策略很少(甚至從未)被認為是重要的設計範式(design paradigm)。
新的分類法自然涵蓋傳統分類法無法歸類的許多經典算法(歐幾裡得算法、堆排序、查找樹、散列法、拓撲排序、高斯消去法和霍納規則等)，所以，新的分類法使我們能以統一和連貫的方式呈現經典算法的標準體系。
它自然適應幾種設計技術的重要變化形式。例如，它能夠涵蓋減治法的三個變種和變治法的三個變種。
進行效率分析時，新的分類法與分析方法更適合(參見附錄B)。
設計技術作為問題求解的一般性策略
本書主要是將算法設計技術應用於計算機科學的經典問題。唯一的創新是加入了一些關於數值算法的內容，這些內容涵蓋在同一個通用框架內。但是，這些設計技術可以用作通用問題求解工具，其應用並不限於傳統的計算和數學問題。有兩個因素使這一點顯得特別重要。首先，越來越多的計算應用超越了傳統領域，而且有理由相信這種趨勢在未來會進一步加強。其次，培養學生解決問題的能力被認為是大學教育的一個主要目標。在計算機科學課程體系中安排一門算法設計與分析課程是非常合適的，因為它可以教會學生如何應用一些特定的策略來解決問題。
我並不是說要把算法設計與分析課程變成一門常規性的問題求解課程。但我真心覺得不宜錯過研究算法設計與分析所帶來的獨特機會。基於此，我在本書中加入了謎題和謎題風格類遊戲的應用。雖然在算法教學中使用謎題不是什麼新鮮事，但本書力求以系統化的方式通過幾個遠遠高於標準的例子來做到這一點。
如何使用本書
我的目標是寫一本既不泛泛而談但又可供學生獨立閱讀的教材。為了實現這個目標，本書做了如下努力。
根據喬治•福賽斯的觀點(參見之前的引文)，我試圖著重強調隱藏於算法設計和分析背後的主要思想。在選擇特定的算法來闡述這些思想的時候，我並不傾向於涉及大量的算法，而是選擇那些最能揭示其基本設計技術或分析方法的算法。值得慶幸的是，大多數經典算法都滿足這個要求。
第2章主要分析算法的效率，該章有意區分了用於分析非遞歸算法的方法和通常用於分析遞歸算法的方法。這一章還花了一些篇幅來介紹算法經驗分析和算法可視化。
書中以系統化的方式穿插了一些面向讀者的提問，其中有些問題是我們精心設計的，而且答案緊隨其後，其目的是引起讀者的注意或引發疑問。其余問題的用意是防止讀者走馬觀花而無法充分理解本書的內容。
每章結尾處都會對當前這一章中最重要的概念和結論做一個總結。
本書包含600多道習題。有些習題供大家練習用，另外一些則是想要指出書中正文部分所涉及內容的重要意義，或是想要介紹書中沒有涉及的一些算法。有一些習題利用了網上的資源。較難的習題數量不多，在教參中用一種特殊的記號標注出來(有的學生可能沒有勇氣做那些有難度標注的習題，所以本書沒有為習題標注難度)。謎題類的習題用一種特殊的圖標做標注。
本書全部習題都附有提示。除了編程練習，習題的詳細解法都能在教師資源中找到。請發送郵件到coo@netease.com，申請教師相關資源(也可聯繫培生的當地銷售代表，或者訪問www.pearsonhighered.com/irc)。
第3版的變化
第3版有若干變化，其中最重要的變化是介紹減治法和分治法的先後順序。第3版先介紹減治法，後介紹分治法，這樣做可以帶來以下優勢。
相比分治法，減治法更簡單。
相比分治法，減治法能解決的問題更多。
新的編排順序便於先介紹插入排序，後介紹合並排序和快速排序。
數組劃分的概念通過選擇問題引入，這次利用Lomuto算法的單向掃描來實現，而將Hoare劃分方法的雙向掃描留到後文與快速排序一並介紹。
折半查找歸入介紹減常量算法的章節。
另一個重要變化是重新編排了第8章關於動態規劃的內容，具體是指導述部分的內容是全新的。在前兩版中用計算二項式系數的例子來引入動態規劃這一重要技術，但第3版介紹了三個基礎性示例，效果更好一些；8.1節的習題是全新的，包括前兩版中沒有涉及的一些流行應用；第8章其他小節的順序有調整，以便達到由淺入深、循序漸進的效果。
此外，還有其他一些變化。增加了不少與本書所述算法相關的應用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的範疇，因為我認為這樣更合理。在介紹生成組合物件的算法時，新增了格雷碼算法。對求解最近對問題的分治法有更深入的探討。改進的內容包括算法可視化和求解旅行商問題的近似算法，當然參考文獻也有相應的更新。
第3版大約新增70道習題，涉及算法謎題和常見的算法面試題。
先修課程
本書假定讀者已經學過離散數學的標準課程和一門基礎性的編程課程。有了這樣的知識背景，讀者應該能夠掌握本書的內容而不會遇到太大的困難。盡管如此，1.4節、附錄A和附錄B仍然對基本的數據結構以及肯定會用到的求和公式與遞推關係進行復習和回顧。只有3個小節(2.2節、11.4節和12.4節)會用到一些簡單的微積分知識，如果讀者缺少必要的微積分知識，完全可以跳過這3個涉及微積分的小節，這樣做並不妨礙大家對本書其余部分的理解。
課程進度安排
如果打算開設一門基礎課來聚焦於算法設計技術，講解算法設計和分析理論，可以採用本書作為教材。但要想在一個學期內完成該課程，本書的內容可能就太豐富了。大體上來說，跳過第3章到第12章的部分內容不會影響讀者對後面部分的理解。本書的任何一個部分都可以安排學生自學。尤其是2.6節和2.7節，它們分別介紹經驗分析和算法可視化，這兩個小節可以結合課後練習一起布置給學生，讓他們課後完成。
以下教學計劃用於一個學期的課程，按照40課時的全日制教學計劃來設計。
課次 主題 小節
1 課程簡介 1.1～1.3
2，3 分析框架；常用符號O、Θ和Ω 2.1，2.2
4 非遞歸算法的數學分析 2.3
5，6 遞歸算法的數學分析 2.4，2.5( 附錄B)
7 蠻力算法 3.1，3.2( 3.3)
8 窮舉查找 3.4
9 深度優先查找和廣度優先查找 3.5
10～11 減一算法：插入排序、拓撲排序 4.1，4.2
12 折半查找和其他減常量算法 4.4
13 減變量算法 4.5
14～15 分治法：合並排序、快速排序 5.1～5.2
16 其他分治法示例 5.3、5.4或5.5
17～19 實例化簡：預排序、高斯消去法、平衡查找樹 6.1～6.3
20 改進性能：堆和堆排序或者霍納法則和二進制冪 6.4或6.5
21 問題化簡 6.6
22～24 時空權衡：串匹配、散列法、B樹 7.2～7.4
25～27 動態規劃算法 8.1～8.4(選學3節)
28～30 貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1～9.4
31～33 迭代改進算法 10.1～10.4(選學3節)
34 下界的參數 11.1
35 決策樹 11.2
36 P、NP和NP完全問題 11.3
37 數值算法 11.4( 12.4)
38 回溯法 12.1
39 分支定界法 12.2
40 NP困難問題的近似算法 12.3
致謝
我要向本書的審閱人員表達衷心的感謝，還要感謝本書前面兩個版本的許多讀者，他們提供了許多寶貴的意見和建議來幫助改進和完善本書。本書第3版尤其得益於下列審閱人員：芝加哥洛約拉大學的Andrew Harrington、聖文德大學的David Levine、加州大學河濱分校的Stefano Lombardi、賓州曼斯菲爾德大學的Daniel McKee、弗吉尼亞州立聯邦大學的Susan Brilliant、菩及海灣大學的David Akers以及兩名匿名評審。
我要感謝培生出版社為本書付出不懈努力的所有工作人員和相關人員。尤其要感謝本書編輯Matt Goldstein、編務助理Chelsea Bell、市場經理Yez Alayan和產品總監Kayla Smith-Tarbox。我還要感謝Richard Camp為本書審稿，感謝Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott為本書排版並提供項目管理支持，感謝MaryEllen Oliver擔任本書校對。
最後，我要感謝我的兩位家人。相比自己寫書，另一半天天忙著寫書更讓人崩潰，我的妻子Maria包容我多年並任勞任怨地幫助我完成書中400多個公式或插圖以及教師手冊。女兒Miriam是我多年的英語老師，她不但閱讀了本書大部分內容，還幫著我為每章找到了恰如其分的名人名言。

阿納尼•樂維汀(Anany Levitin)

詳細目錄
第1章　導言 1
1.1　什麼是算法 3
習題1.1 8
1.2　算法問題求解基礎 9
1.2.1 理解問題 10
1.2.2 了解計算設備的性能 11
1.2.3 在精確和近似解法之間做出選擇 12
1.2.4 算法的設計技術 12
1.2.5 設計算法和數據結構 12
1.2.6 算法描述方法 13
1.2.7 算法的正確性證明 14
1.2.8 分析算法 14
1.2.9 為算法寫代碼 16
習題1.2 17
1.3　重要的問題類型 19
1.3.1 排序 19
1.3.2 查找 21
1.3.3 字符串處理 21
1.3.4 圖問題 22
1.3.5 組合問題 22
1.3.6 幾何問題 23
1.3.7 數值問題 23
習題1.3 24
1.4　基本數據結構 26
1.4.1 線性數據結構 26
1.4.2 圖 29
1.4.3 樹 32
1.4.4 集合與字典 36
習題1.4 38
本章要點小結 39
第2章　算法效率分析基礎 41
2.1　分析框架 42
2.1.1 度量輸入規模 43
2.1.2 運行時間的度量單位 44
2.1.3 增長量級 45
2.1.4 算法的最差、最優和平均效率 47
2.1.5 分析框架概要 50
習題2.1 50
2.2　漸近符號和基本效率類型 52
2.2.1 非正式的介紹 53
2.2.2 符號O 53
2.2.3 符號Ω 54
2.2.4 符號Θ 55
2.2.5 漸近符號的有用特性 56
2.2.6 利用極限比較增長量級 57
2.2.7 基本效率類別 58
習題2.2 60
2.3 非遞歸算法的數學分析 61
習題2.3 67
2.4 遞歸算法的數學分析 70
習題2.4 77
2.5　例題：計算第n個斐波那契數 80
習題2.5 84
2.6　算法的經驗分析 85
習題2.6 91
2.7　算法可視化 92
本章要點小結 95
第3章　蠻力法 97
3.1　選擇排序和冒泡排序 98
3.1.1 選擇排序 98
3.1.2 冒泡排序 100
習題3.1 102
3.2　順序查找和蠻力字符串匹配 103
3.2.1 順序查找 104
3.2.2 蠻力字符串匹配 104
習題3.2 106
3.3　最近對和凸包問題的蠻力算法 108
3.3.1 最近對問題 108
3.3.2 凸包問題 110
習題3.3 113
3.4　窮舉查找 115
3.4.1 旅行商問題 116
3.4.2 背包問題 117
3.4.3 分配問題 119
習題3.4 120
3.5　深度優先查找和廣度優先查找 122
3.5.1 深度優先查找 122
3.5.2 廣度優先查找 125
習題3.5 128
本章要點小結 130
第4章　減治法 132
4.1　插入排序 135
習題4.1 137
4.2　拓撲排序 140
習題4.2 143
4.3 生成組合物件的算法 145
4.3.1 生成排列 145
4.3.2 生成子集 148
習題4.3 150
4.4 減常因子算法 151
4.4.1 折半查找 152
4.4.2 假幣問題 154
4.4.3 俄式乘法 155
4.4.4 約瑟夫斯問題 156
習題4.4 158
4.5　減可變規模算法 160
4.5.1 計算中值和選擇問題 160
4.5.2 插值查找 164
4.5.3 二叉查找樹的查找和插入 165
4.5.4 尼姆遊戲 166
習題4.5 168
本章要點小結 170
第5章　分治法 171
5.1　合並排序 173
習題5.1 176
5.2　快速排序 178
習題5.2 183
5.3　二叉樹遍歷及其相關特性 185
習題5.3 188
5.4　大整數乘法和Strassen矩陣乘法 189
5.4.1 大整數乘法 190
5.4.2 Strassen矩陣乘法 192
習題5.4 194
5.5　用分治法解最近對問題和凸包問題 195
5.5.1 最近對問題 195
5.5.2 凸包問題 198
習題5.5 200
本章要點小結 201
第6章　變治法 203
6.1　預排序 204
習題6.1 207
6.2　高斯消去法 210
6.2.1 LU分解 215
6.2.2 計算矩陣的逆 216
6.2.3 計算矩陣的行列式 217
習題6.2 218
6.3　平衡查找樹 220
6.3.1 平衡二叉查找樹 221
6.3.2 2-3樹 225
習題6.3 228
6.4　堆和堆排序 229
6.4.1 堆的概念 229
6.4.2 堆排序 234
習題6.4 235
6.5　霍納法則和二進制冪 236
6.5.1 霍納法則 237
6.5.2 二進制冪 239
習題6.5 242
6.6　問題化簡 243
6.6.1 求最小公倍數 244
6.6.2 計算圖中的路徑數量 245
6.6.3 最優化問題的化簡 246
6.6.4 線性規劃 247
6.6.5 簡化為圖問題 250
習題6.6 251
本章要點小結 253
第7章　時空權衡 255
7.1　計數排序 256
習題7.1 260
7.2　字符串匹配中的輸入增強技術 261
7.2.1　Horspool算法 262
7.2.2　Boyer-Moore算法 265
習題7.2 270
7.3　散列法 271
7.3.1　開散列(分離鏈) 273
7.3.2　閉散列(開式尋址) 275
習題7.3 278
7.4　B樹 279
習題7.4 283
本章要點小結 284
第8章　動態規劃 285
8.1　三個基本例子 287
習題8.1 292
8.2　背包問題和記憶功能 295
8.2.1 背包問題 295
8.2.2　記憶功能 297
習題8.2 298
8.3　最優二叉查找樹 299
習題8.3 304
8.4　Warshall算法和Floyd算法 305
8.4.1　Warshall算法 306
8.4.2　計算完全最短路徑的Floyd算法 309
習題8.4 313
本章要點小結 314
第9章　貪婪技術 315
9.1　Prim算法 318
習題9.1 323
9.2　Kruskal算法 325
習題9.2 332
9.3　Dijkstra算法 334
習題9.3 338
9.4　哈夫曼樹及編碼 339
習題9.4 343
本章要點小結 344
第10章　迭代改進 346
10.1　單純形法 347
10.1.1 線性規劃的幾何解釋 348
10.1.2 單純形法概述 352
10.1.3 單純形法其他要點 358
習題10.1 360
10.2　最大流量問題 362
習題10.2 372
10.3　二分圖的最大匹配 373
習題10.3 380
10.4　穩定婚姻問題 382
習題10.4 386
本章要點小結 387
第11章　算法能力的極限 388
11.1　如何求下界 389
11.1.1　平凡下界 390
11.1.2　信息論下界 391
11.1.3　敵手下界 391
11.1.4　問題化簡 393
習題11.1 394
11.2　決策樹 396
11.2.1　排序的決策樹 397
11.2.2　查找有序數組的決策樹 399
習題11.2 401
11.3　P、NP和NP完全問題 403
11.3.1　P和NP問題 403
11.3.2　NP完全問題 407
習題11.3 411
11.4　數值算法的挑戰 414
習題11.4 421
本章要點小結 422
第12章　應對算法能力的極限 425
12.1　回溯法 426
12.1.1　n皇后問題 427
12.1.2　哈密頓回路問題 428
12.1.3　子集和問題 429
12.1.4　概括性說明 430
習題12.1 432
12.2　分支定界法 434
12.2.1　分配問題 435
12.2.2　背包問題 437
12.2.3　旅行商問題 440
習題12.2 442
12.3　NP難題的近似算法 443
12.3.1　旅行商問題的近似算法 445
12.3.2　背包問題的近似算法 454
習題12.3 459
12.4　解非線性方程的算法 460
12.4.1　對分法 462
12.4.2　試位法 465
12.4.3　牛頓法 466
習題12.4 468
本章要點小結 469
後記 472
附錄A　算法分析的實用公式 477
附錄B　遞推關係簡明指南 480
參考文獻 494