第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
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
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
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
· · · · · · (收起)