An Introduction to the Analysis of Algorithms
暫譯: 演算法分析入門

這本書全面概述了在算法數學分析中使用的主要技術和模型。書的前半部分基於離散數學、初等實分析和組合學的經典數學材料；後半部分討論離散結構的性質，並涵蓋各種經典排序、搜尋和字串處理算法的分析。

目錄
1. 算法分析。
為什麼要分析算法？
計算複雜度。
算法分析。
平均情況分析。
範例：快速排序的分析。
漸近近似。
分佈。
機率算法。

2. 遞迴關係。
基本性質。
一階遞迴。
非線性一階遞迴。
高階遞迴。
解遞迴的方法。
二元分治遞迴和二進位數。
一般分治遞迴。

3. 生成函數。
普通生成函數。
指數生成函數。
遞迴的生成函數解。
展開生成函數。
使用生成函數的變換。
生成函數上的函數方程。
解決快速排序的三數中位數。
使用OGFs的遞迴。
使用生成函數的計數。
符號方法。
拉格朗日反演。
機率生成函數。
二元生成函數。
特殊函數。

4. 漸近近似。
漸近近似的符號。
漸近展開。
操作漸近展開。
有限和的漸近近似。
歐拉-馬克勞林求和。
二元漸近。
拉普拉斯方法。
來自算法分析的「正常」範例。
來自算法分析的「泊松」範例。
生成函數的漸近性質。

5. 樹。
二元樹。
樹和森林。
樹的性質。
樹算法。
二元搜尋樹。
卡塔蘭樹的平均路徑長度。
二元搜尋樹的路徑長度。
隨機樹的加性參數。
高度。
樹的性質的平均情況結果總結。
樹和二元樹的表示法。
無序樹。
標記樹。
其他類型的樹。

6. 排列。
排列的基本性質。
排列上的算法。
排列的表示法。
列舉問題。
使用CGFs分析排列的性質。
反轉和插入排序。
從左到右的最小值和選擇排序。
週期和原地排列。
極值參數。

7. 字串和字典樹。
字串搜尋。
位元串的組合性質。
正規表達式。
有限狀態自動機和Knuth-Morris-Pratt算法。
上下文無關文法。
字典樹。
字典樹算法。
字典樹的組合性質。
更大的字母表。

8. 字和映射。
使用分離鏈接的雜湊。
字的基本性質。
生日悖論和抽獎問題。
占用限制和極值參數。
占用分佈。
開放地址雜湊。
映射。
整數分解和映射。