算法分析导论（第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博士是法国科学院院士。

第 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