算法分析导论（第2版）

第 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