算法分析導論（第2版） An Introduction to the Analysis of Algorithms, 2/e)

【美】罗伯特·塞奇威克（Robert Sedgewick）

曾在斯坦福大学师从唐纳德·E.克努特院士，获得博士学位。他于1985年开始在普林斯顿大学任教，是该校计算机科学系的创始人，现任该校计算机科学系教授。他曾是Adobe Systems公司董事会成员，并在Xerox PARC、IDA 和 INRIA等机构从事研究工作。他是算法领域入门作品 Algorithms（Fourth Edition）的作者。

 

【法】费利佩·弗拉若莱（Philippe Flajolet）

法国科学院院士，曾任法国国家信息与自动化研究所（INRIA）的资深研究总监，创建并领导了 ALGO 研究小组。他因在算法分析领域的开创性研究而声名鹊起，他在分析组合学领域梳理并发展出了强大的新方法，解决了很多悬而未决的难题，并在世界各地进行算法分析的教学。

第 1 章 算法分析 1

1.1　為什麽要做算法分析　1

1.2　算法理論　2

1.3　算法分析概述　6

1.4　平均情況分析　7

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

1.6　漸近近似　14

1.7　分佈　15

1.8　隨機算法　17

參考資料　19

第　2 章 遞歸關系　21

2.1　基本性質　22

2.2　一階遞歸　24

2.3　一階非線性遞歸　27

2.4　高階遞歸　29

2.5　求解遞歸的方法　32

2.6　二分分治遞歸和二進制數　37

2.7　一般的分治遞歸　44

參考資料　48

第　3 章 母函數　50

3.1　普通型母函數　50

3.2　指數型母函數　54

3.3　利用母函數求解遞歸　56

3.4　母函數的展開　62

3.5　利用母函數進行變換　64

3.6　關於母函數的函數方程　66

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

3.8　利用母函數計數　70

3.9　概率母函數　73

3.10　雙變量母函數　75

3.11　特殊函數　79

參考資料　84

第　4 章 漸近逼近　86

4.1　漸近逼近的概念　87

4.2　漸近展開式　91

4.3　處理漸近展開式　96

4.4　有限和的漸近逼近　101

4.5　歐拉-麥克勞林求和　103

4.6　二元漸近　108

4.7　拉普拉斯方法　117

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

4.9　算法分析中的“泊松”舉例　122

參考資料　125

第　5 章 分析組合　126

5.1　正式的基礎　126

5.2　無標記類的符號方法　127

5.3　有標記類的符號方法　132

5.4　參數的符號方法　139

5.5　母函數系數逼近　142

參考資料　147

第　6 章 樹　148

6.1　二叉樹　148

6.2　森林和樹　150

6.3　樹和二叉樹的組合等價　152

6.4　樹的性質　157

6.5　樹算法的例子　159

6.6　二叉搜索樹　162

6.7　隨機 Catalan 樹　165

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

6.9　隨機樹的附加參數　172

6.10　高度　174

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

6.12　拉格朗日反演　180

6.13　無序樹　182

6.14　標記樹　189

6.15　其他類型的樹　192

參考資料　197

第　7 章 排列　199

7.1　排列的基本性質　200

7.2　排列算法　204

7.3　排列的表示法　206

7.4　計數問題　210

7.5　通過 CGF 分析排列的性質　214

7.6　逆序和插入排序　221

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

7.8　環與原地排列　231

7.9　極值參數　233

參考資料　237

第　8 章 字符串與字典樹　238

8.1　字符串搜索　239

8.2　位串的組合性質　241

8.3　正則表達式　248

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

8.5　上下文無關的語法　254

8.6　字典樹　258

8.7　字典樹算法　261

8.8　字典樹的組合性質　265

8.9　更大的字符表　269

參考資料　271

第　9 章 單詞與映射　273

9.1　使用分離鏈接的散列　273

9.2　球與瓮的模型和單詞的性質　275

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

9.4　占據限制與極值參數　286

9.5　占據分佈　290

9.6　開放尋址散列法　295

9.7　映射　301

9.8　整數因子分解與映射　309

參考資料　312