算法分析導論(第2版)（簡體書）

本書全面介紹了算法的數學分析所涉及的主要技術。涵蓋的內容來自經典的數學課題（包括離散 數學、初等實分析、組合數學），以及經典的計算機科學課題（包括算法和數據結構）。本書的重點是“平均情況”或“概率性”分析，書中也論述了“最差情況”或“複雜性”分析所需的基本數學工具。本書第1 版為行業代表性著作，第2 版不僅對書中圖片和代碼進行了更新，還補充了新章節。全書共9 章，第1 章是導論；第2～5 章介紹數學方法；第6～9 章介紹組合結構及其在算法分析中的應用。除每章包含的大量習題以及參考文獻外，本書特設配套免費學習網站，為讀者提供了很多關於算法分析的補充材料，包括課件和相關網站的鏈接，幫助讀者提高學習興趣，完成更深入的學習。

Robert Sedgewick於1985年開始在普林斯頓大學任教，是該校計算機系的創始人，現任該校計算機科學系教授。他曾任Adobe Systems公司董事會成員，並在Xerox PARC、IDA和INRIA等機構從事研究。他是算法領域入門著作Algorithms（Fourth Edition）的作者。Sedgewick教授在斯坦福大學師從D. E. Knuth院士，獲得博士學位。

Philippe Flajolet曾任法國羅克庫爾INRIA資深研究總監，創建並領導了ALGO研究組。他因在算法分析領域的開創性研究而聲名鵲起，在分析組合學方面梳理併發展出了強大的新方法，解決了很多長期懸而未決的難題，並在世界各地從事算法分析的教學。Flajolet博士是法國科學院院士。

譯者序
公元 2014年的冬天，一部講述計算機科學之父艾倫·圖靈（ Alan Turing）傳奇人生的傳記電影在美國上映，這部影片就是《模仿遊戲》。次年，該片榮獲第 87屆奧斯卡金像獎最佳改編劇本獎，以及包括最佳影片、最佳導演、最佳男主角、最佳女配角在內的 7項提名，一時風光無限。
圖靈一生最重要的三大貢獻包括圖靈機、圖靈測試，以及破譯 Enigma密碼機，其中的每一項都值得全世界感謝和紀念他。在提出圖靈測試的論文中，圖靈石破天驚地預言了創造出具有真正智能的機器的可能性，這也是後來人工智能研究的源頭。事實上，《模仿遊戲》這個名字正是圖靈那篇著名論文第 1章的標題。後人為了紀念圖靈對計算機科學所做出的巨大貢獻，也將該領域的最高獎命名為“圖靈獎”。另一方面，破譯 Enigma密碼更是直接幫助盟軍在戰場上取得先機，甚至拯救了無數人的性命並最終導致第二次世界大戰反法西斯陣營的全面勝利。
儘管前面提到的兩大貢獻已是功若丘山，但筆者這裡將從圖靈的另外一個貢獻― ―“圖靈機”談起，因為這與本書所要討論的話題息息相關。不過，為此我們還得把時間再往前推。1900年，德國數學家大衛·希爾伯特（ David Hilbert）在巴黎舉行的國際數學家大會上做了題為《數學問題》的演講。在這篇重要的演講中，他提出了著名的希爾伯特之 23個問題。儘管此後的數學發展遠遠超過了希爾伯特的預料，但他所提出的 23個問題仍然對 20世紀的數學發展起到了重要的推動作用。
希爾伯特的第 10個問題是要設計一個算法來測試多項式是否有整數根。他沒有使用“算法”這個術語，而是採用了下面這種表述：“通過有限多次運算就可以決定的過程。”有意思的是，從希爾伯特對這個問題的陳述中可以看出，他明確地要求設計一個算法。因此，他顯然是假設這樣的算法存在，人們所要做的只是找到它。現在我們知道，這個任務是無法完成的，即它是算法上不可解的。但對那個時期的數學家來說，以他們對算法的直觀認
算法分析導論（第 2版）
識，得出這樣的結論是不可能的。非形式地說，算法是為實現某個任務而構造的簡單指令集。用日常用語來說，算法又被稱為過程或者方法。算法在數學中也起著非常重要的作用。古代數學文獻中就包含執行各種各樣計算任務的算法描述。例如，我國古代數學經典《九章算術》中就記述了包括求最大公約數、最小公倍數、開平方根、開立方根等在內的諸多算法。雖然算法在數學中已有很長的歷史，但在 20世紀之前，算法本身一直沒有精確的定義。數學家們面對希爾伯特的第 10個問題顯得束手無策。由於缺乏對算法本身的精確定義，所以要證明某個特定任務不存在算法就更不可能了。要想破解希爾伯特的第 10個問題，人們不得不等待算法的精確定義的出現。直到 1936年，曙光似乎出現了。圖靈向倫敦的權威數學雜誌遞交了一篇題為《論數字計算在決斷難題中之應用》的論文。該文最終於 1937年正式發表，並立即引起了廣泛關注。在論文中，圖靈描述了一種可以輔助數學研究的機器，也就是後來被稱為“圖靈機”的抽象系統。與此同時，另外一位數學家阿隆佐·丘奇（ Alonzo Church）也獨立地提出了另外一套系統，即所謂的 Lambda演算。圖靈採用他的圖靈機來定義算法，而丘奇則採用 Lambda演算來定義算法，後來圖靈證明這兩個定義是等價的。由此，人們在算法的非形式概念和精確定義之間建立了聯繫，即算法的直覺概念等價於圖靈機，這就是所謂的“丘奇－圖靈”論題。“丘奇－圖靈”論題提出的算法定義是解決希爾伯特第 10個問題所需的。而第 10個問題的真正解決則要等到 1970年，借助於丘奇與圖靈的傑出貢獻，馬提亞塞維齊（ Yuri Matiyasevich）在戴維斯（Martin Davis）、普特納姆（Hilary Putnam）和羅賓遜（Julia Robinson）等人工作的基礎上，最終證明檢查多項式是否有整數根的算法是不存在的。上述四人的名字也緊緊地同希爾伯特的第 10個問題聯繫在了一起。破解希爾伯特的第 10個問題的過程更像一場聲勢浩大又曠日持久的國際協作和學術接力。每個人的工作都必不可少，而且大家都感覺已經相當接近問題的最終答案。後來的歷史見證了馬提亞塞維齊敏銳地接過最後一棒並完成終點衝刺的偉大一幕。更有意思的是，彼時正值美蘇冷戰最為緊張的時期，兩個超級大國之間的正常學術交流幾乎完全中斷。但這或許就是科學無國界的一個重要體現，儘管國家層面上雙方劍拔弩張，而科學家在私下仍然以一種惺惺相惜的默契方式彼此神交。特別是在得知蘇聯數學家完成了最終的證明時，美國同行都表現得相當振奮和由衷的喜悅，這不得不說是學術界的一段佳話。回顧建立算法形式化定義和破解希爾伯特之第 10個問題的那段風起雲湧的歷史，我們不得不由衷地感歎：算法對於我們的世界是多麼重要。可以這樣說，自計算機科學誕生之日起，關於算法的研究就一直是一個核心話題。現代計算機科學中充滿了各種各樣的算法，
譯者序 V
許多圖靈獎得主也正是因提出的各種經典算法而聞名於世。例如，提出單源最短路徑算法的迪可斯特朗（ Edsger Dijkstra）①、提出字符串匹配算法的高德納（ Donald Knuth）②、提出多源最短路徑算法的弗洛伊德（ Robert Floyd）③，以及提出快速排序算法的霍爾（ Antony Hoare）④等。其中，高德納是最年輕的圖靈獎得主這一紀錄的保持者（獲獎時年僅 36歲），並以計算機算法設計與分析領域的經典巨著《計算機程序設計藝術》而廣為人知。
作為導師，高德納一生共指導過 28位博士生，而本書作者之一的羅伯特·塞奇威克（Robert Sedgewick）便是其中之一。塞奇威克曾經是普林斯頓大學計算機科學系的創立者暨
首任系主任，他同時還是著名的 Adobe公司的董事。作為一位世界知名的計算機科學家，
塞奇威克於 1997年當選 ACM（Association for Computing Machinery，國際計算機學會）院
士，並因從“對稱二叉樹”中導出了紅黑樹而享譽計算機界。
塞奇威克與費利佩·弗拉若萊（ Philippe Flajolet）曾合作撰寫過數本算法分析領域的著作，本書即為其中一部在全世界範圍內廣泛流傳的經典之作。弗拉若萊是一名法國計算機科學家，法國科學院院士，同時也被稱為“分析組合學之父”。他與合作者共同提出的 Flajolet-Martin算法更是當今互聯網與大數據時代背景下，網站分析統計的重要基石。
然而，天妒英才， 2011年 3月，休假期間的塞奇威克驚悉多年的老友弗拉若萊突然離世。悲痛萬分的塞奇威克懷著對逝者的無限緬懷寫了感人至深的悼詞：“弗拉若萊的離世意味著很多秘密再也無法揭開。但他給世人留下了很多追隨他腳步的繼承者，他們可再續他的數學夢想。”在這樣的背景下，塞奇威克以極大的熱情投入工作，歷經數百個日夜，終於在 2012年 10月將本書的第 2版付梓。塞奇威克堅信弗拉若萊的精神會在後來人的工作中得到永生，進而希冀本書讀者能夠循著弗拉若萊的腳步，繼續追求他的數學夢想。
本書全面系統地介紹了算法分析中需要使用的基本技術，所涉及的內容既來自包括離散數學、組合數學、概率論等在內的經典數學問題，也有來自算法及數據結構等計算機科學問題。像遞歸、母函數、樹形結構、字符串、映射以及散列等算法分析話題均有討論。可以說本書是一本研究算法分析的權威之作。
作為譯者，我們希望自圖靈以來的算法研究能夠在更寬闊的範圍內，被更光大地發揚，尤其希望中國的計算機科研人員能夠從本書中找到啟迪研究工作的智慧。同時，也希望通過本書向神交已久的兩位大師――弗拉若萊和塞奇威克送上最崇高的敬意。
① 1972年圖靈獎得主。

② 1974年圖靈獎得主。

③ 1978年圖靈獎得主。

④ 1980年圖靈獎得主。


算法分析導論（第 2版）
最後，本書翻譯工作的完成有賴於數位合作者的傾心付出，其中常青翻譯了本書的第 1至 6章、左飛翻譯了第 8、9章、于佳平翻譯了第 7章。其他參與本書翻譯和校對工作的人員還有李振坡、邵臣、葉劍、趙冰冰、賈嘯天、錢文秀、丁星芸、李曉華、黃帥。自知論道須思量，幾度無眠一文章。因時間和水平有限，紕漏與不足之處在所難免，譯者懇切地期望廣大同行及讀者朋友不吝批評斧正。

序
分析算法可以給人帶來兩方面的快樂。其一，人們可以盡享優雅計算過程中所蘊含的讓人沉醉的數學模式；其二，我們所學到的理論知識可以讓自己更好更快地完成工作，這無疑是最實際的好處。
儘管數學模型只是對真實世界的一種理想化近似，但它對所有的科學活動而言都可謂是一劑靈丹妙藥。在計算機科學中，數學模型往往可以精確地描述計算機程序所創造的世界，數學模型的重要性也因此大大增加了。我想，這也是為什麼我在讀研究生時會沉迷于算法分析，以至於這成為我迄今為止的主要工作。
但直到今天，算法分析在很大程度上還是局限在相關專業的研究生和科研人員的圈子裡。算法分析的概念既不晦澀也不複雜，但確實比較新，所以相關概念的學習和使用都還需要一些時間才能成熟。
現在，經過 40餘年的發展，算法分析已經非常成熟，足以成為計算機專業標準課程中的一部分。 Sedgewick和 Flajolet寫的這本眾人翹首以盼的教科書也因此備受歡迎。本書的作者不僅僅是這個領域的世界級專家，同時也是算法分析的佈道大師。我堅信，這本書會讓每一位細細品讀的計算機研究人員從中獲益。
D. E. Knuth

前言
本書的主要目的是介紹算法的數學分析中涉及的主要技術。涵蓋的內容都來自經典的數學和計算科學領域，包括來自數學領域的離散數學、實分析基礎和組合數學，來自計算機領域的算法和數據結構等。本書的重點是“平均情況”或是“概率性”的分析，對“最差情況”或“複雜度”分析所需的基本數學工具也有所涉及。
我們假設讀者對計算機科學和實分析的基本概念是比較熟悉的。簡單來說，讀者要能夠編寫程序和證明定理

目錄
第 1章算法分析 ............... 1

1.1 為什麼要做算法分析 ..........................................................1

1.2 算法理論 ..................3

1.3 算法分析概述 ..........8

1.4 平均情況分析 ........10

1.5 實例：快速排序算法的分析 ............................................12

1.6 漸近近似 ................ 18

1.7 分佈 ........................ 20

1.8 隨機算法 ................ 22
參考文獻 ......................... 25

第 2章遞歸關係 ............. 28

2.1 基本性質 ................ 29

2.2 一階遞歸 ................ 33

2.3 一階非線性遞歸 ....35

2.4 高階遞歸 ................ 38

2.5 求解遞歸的方法 ....42

2.6 二分分治遞歸和二進制數 ................................................49

2.7 一般的分治遞歸 ....57
參考文獻 ......................... 62

第 3章母函數 .................. 64

3.1 普通型母函數 ........65

算法分析導論（第 2版）
3.2 指數型母函數 .........69

3.3 利用母函數求解遞歸 ........................................................72

3.4 母函數的展開 .........79

3.5 利用母函數進行變換 ........................................................82

3.6 關於母函數的函數方程 ....................................................84

3.7 利用 OGF求解三項中值 Quicksort遞歸.........................87

3.8 利用母函數計數 .....89

3.9 概率母函數 .............93

3.10 雙變量母函數 .......96

3.11特殊函數.............101
參考文獻........................107

第 4章漸近逼近 ........... 109

4.1 漸近逼近的概念 ...111

4.2 漸近展開式 ...........116

4.3 處理漸近展開式 ...123

4.4 有限和的漸近逼近 ..........................................................129

4.5 歐拉-麥克勞林求和 ........................................................131

4.6 二元漸近...............137

4.7 拉普拉斯方法 .......149

4.8 算法分析中的“正態”舉例 ..........................................152

4.9 算法分析中的“泊松”舉例 ..........................................155
參考文獻........................159

第 5章分析組合 ........... 161

5.1 正式的基礎 ...........162

5.2 無標記類的符號方法 ......................................................163

5.3 有標記類的符號方法 ......................................................169

5.4 參數的符號方法 ...177

5.5 母函數係數逼近 ...182
參考文獻........................188

第 6章樹........................ 189

6.1 二叉樹...................190

目錄 XV
6.2 森林和樹 .............. 192

6.3 樹和二叉樹的組合等價 ..................................................194

6.4 樹的性質 .............. 200

6.5 樹算法的例子 ......204

6.6 二叉搜索樹 .......... 207

6.7 隨機 Catalan樹 .... 211

6.8 二叉搜索樹中的路徑長度 .............................................. 216

6.9 隨機樹的附加參數 .........................................................219

6.10 高度 .................... 223

6.11樹屬性在平均情況下的結果總結 ................................229

6.12 拉格朗日反演 ....230

6.13 無序樹 ................ 233

6.14 標記樹 ................ 242

6.15 其他類型的樹 ....245
參考文獻 ....................... 253

第 7章排列 ....................256

7.1 排列的基本性質 .. 257

7.2 排列算法 .............. 263

7.3 排列的表示法 ......266

7.4 計數問題 .............. 271

7.5 通過 CGF分析排列的性質............................................275

7.6 逆序和插入排序 .. 285

7.7 從左到右最小值和選擇排序 ..........................................291

7.8 環與原地排列 ......297

7.9 極值參數 .............. 300
參考文獻 ....................... 304

第 8章字符串與字典樹 .........................................................306

8.1 字符串搜索 .......... 307

8.2 位串的組合性質 .. 310

8.3 正則表達式 .......... 320

8.4 有窮狀態自動機和 KMP算法 .......................................323

8.5 上下文無關的語法 .........................................................326

算法分析導論（第 2版）
8.6 字典樹...................332

8.7 字典樹算法 ...........336

8.8 字典樹的組合性質 ..........................................................340

8.9 更大的字符表 .......345
參考文獻........................347

第 9章單詞與映射 ...... 350

9.1 使用分離鏈接的散列 ......................................................351

9.2 球與甕的模型和單詞的性質 ..........................................353

9.3 生日悖論與優惠券收集者問題 ......................................360

9.4 佔據限制與極值參數 ......................................................367

9.5 佔據分佈...............372

9.6 開放尋址散列法 ...379

9.7 映射.......................386

9.8 整數因子分解與映射 ......................................................396
參考文獻........................401