算法分析导论（第2版）
目录
第 1章算法分析 ............... 1
1.1 为什么要做算法分析 ..........................................................1
1.2 算法理论 ..................3
1.3 算法分析概述 ..........8
1.4 平均情况分析 ........10
1.5 实例：快速排序算法的分析 ............................................12
1.6 渐近近似 ................ 18
查看完整
第 1章算法分析 ............... 1
1.1 为什么要做算法分析 ..........................................................1
1.2 算法理论 ..................3
1.3 算法分析概述 ..........8
1.4 平均情况分析 ........10
1.5 实例：快速排序算法的分析 ............................................12
1.6 渐近近似 ................ 18
查看完整
Robert Sedgewick于1985年开始在普林斯顿大学任教，是该校计算机系的创始人，现任该校计算机科学系教授。他曾任Adobe Systems公司董事会成员，并在Xerox PARC、IDA和INRIA等机构从事研究。他是算法领域入门著作Algorithms（Fourth Edition）的作者。Sedgewick教授在斯坦福大学师从D. E. Knuth院士，获得博士学位。
Philippe Flajolet曾任法国罗克库尔INRIA资深研究总监，创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起，在分析组合学方面梳理并发展出了强大的新方法，解决了很多长期悬而未决的难题，并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。
Philippe Flajolet曾任法国罗克库尔INRIA资深研究总监，创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起，在分析组合学方面梳理并发展出了强大的新方法，解决了很多长期悬而未决的难题，并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。
本书全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。本书的重点是“平均情况”或“概率性”分析，书中也论述了“至差情况”或“复杂性”分析所需的基本数学工具。本书第 1 版为行业代表性著作，第 2 版不仅对书中图片和代码进行了更新，还补充了新章节。全书共 9 章，第 1 章是导论；第 2～5 章介绍数学方法；第 6～9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，本书特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习。本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员和爱好者学习参考。
目录
第 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
^ 收 起
第 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
^ 收 起
Robert Sedgewick于1985年开始在普林斯顿大学任教，是该校计算机系的创始人，现任该校计算机科学系教授。他曾任Adobe Systems公司董事会成员，并在Xerox PARC、IDA和INRIA等机构从事研究。他是算法领域入门著作Algorithms（Fourth Edition）的作者。Sedgewick教授在斯坦福大学师从D. E. Knuth院士，获得博士学位。
Philippe Flajolet曾任法国罗克库尔INRIA资深研究总监，创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起，在分析组合学方面梳理并发展出了强大的新方法，解决了很多长期悬而未决的难题，并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。
Philippe Flajolet曾任法国罗克库尔INRIA资深研究总监，创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起，在分析组合学方面梳理并发展出了强大的新方法，解决了很多长期悬而未决的难题，并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。
本书全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。本书的重点是“平均情况”或“概率性”分析，书中也论述了“至差情况”或“复杂性”分析所需的基本数学工具。本书第 1 版为行业代表性著作，第 2 版不仅对书中图片和代码进行了更新，还补充了新章节。全书共 9 章，第 1 章是导论；第 2～5 章介绍数学方法；第 6～9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，本书特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习。本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员和爱好者学习参考。
比价列表
