算法分析导论（第2版）

图书标准信息

• 作者 [美]Robert Sedgewick(罗伯特·塞奇威克；[法]Philippe Flajolet(费利佩·弗拉若莱
• 出版社 电子工业出版社
• 出版时间 2018-11
• 版次 2
• ISBN 9787121353680
• 定价 128.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

《算法分析导论（第2版）》全面介绍了算法的数学分析所涉及的主要技术。涵盖的内容来自经典的数学课题（包括离散数学、初等实分析、组合数学），以及经典的计算机科学课题（包括算法和数据结构）。本书的重点是“平均情况”或“概率性”分析，书中也论述了“*差情况”或“复杂性”分析所需的基本数学工具。
  《算法分析导论（第2版）》第 1 版为行业代表性著作，第 2 版不仅对书中图片和代码进行了更新，还补充了新章节。《算法分析导论（第2版）》共 9 章，第 1 章是导论；第 2～5 章介绍数学方法；第 6～9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，《算法分析导论（第2版）》特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习。
  《算法分析导论（第2版）》适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员和爱好者学习参考。

【作者简介】

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

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

参考文献