《算法分析导论（第2版）》

编辑推荐

√算法分析是推动现代计算基础技术发展的重要力量，《算法分析导论（第2版）》囊括众多算法分析的应用实例。

√无数人对从数学角度分析算法产生兴趣，但很难学到相关方法和模型，《算法分析导论（第2版）》完整介绍该领域主要技术和成果。

√作者既精通经典数学又熟谙计算机科学，看重用于算法性能预测的数学基础及从性能角度比较算法。

√天才般贯通与揭露数学世界的离散数学|分析组合学|实分析与计算机科学领域的算法|数据结构之奥义。

内容简介

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

作者简介

RobertSedgewick于1985年开始在普林斯顿大学任教，是该校计算机系的创始人，现任该校计算机科学系教授。他曾任AdobeSystems公司董事会成员，并在XeroxPARC、IDA和INRIA等机构从事研究。他是算法领域入门著作Algorithms（FourthEdition）的作者。Sedgewick教授在斯坦福大学师从D.E.Knuth院士，获得博士学位。

PhilippeFlajolet曾任法国罗克库尔INRIA资深研究总监，创建并领导了ALGO研究组。他因在算法分析领域的开创性研究而声名鹊起，在分析组合学方面梳理并发展出了强大的新方法，解决了很多长期悬而未决的难题，并在世界各地从事算法分析的教学。Flajolet博士是法国科学院院士。

精彩书评

Sedgewick和Flajolet不仅是算法分析领域的专家，同时也是算法分析的布道大师。我坚信，这《算法分析导论（第2版）》会让每一位细细品读的计算机研究人员从中获益。

——摘自D.E.Knuth为《算法分析导论（第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

前言/序言

译者序

公元2014年的冬天，一部讲述计算机科学之父艾伦·图灵（AlanTuring）传奇人生的传记电影在美国上映，这部影片就是《模仿游戏》。次年，该片荣获第87届奥斯卡金像奖最佳改编剧本奖，以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的7项提名，一时风光无限。

图灵一生最重要的三大贡献包括图灵机、图灵测试，以及破译Enigma密码机，其中的每一项都值得全世界感谢和纪念他。在提出图灵测试的论文中，图灵石破天惊地预言了创造出具有真正智能的机器的可能性，这也是后来人工智能研究的源头。事实上，《模仿游戏》这个名字正是图灵那篇著名论文第1章的标题。后人为了纪念图灵对计算机科学所做出的巨大贡献，也将该领域的最高奖命名为“图灵奖”。另一方面，破译Enigma密码更是直接帮助盟军在战场上取得先机，甚至拯救了无数人的性命并最终导致第二次世界大战反法西斯阵营的全面胜利。

尽管前面提到的两大贡献已是功若丘山，但笔者这里将从图灵的另外一个贡献——“图灵机”谈起，因为这与《算法分析导论（第2版）》所要讨论的话题息息相关。不过，为此我们还得把时间再往前推。1900年，德国数学家大卫·希尔伯特（DavidHilbert）在巴黎举行的国际数学家大会上做了题为《数学问题》的演讲。在这篇重要的演讲中，他提出了著名的希尔伯特之23个问题。尽管此后的数学发展远远超过了希尔伯特的预料，但他所提出的23个问题仍然对20世纪的数学发展起到了重要的推动作用。

希尔伯特的第10个问题是要设计一个算法来测试多项式是否有整数根。他没有使用“算法”这个术语，而是采用了下面这种表述：“通过有限多次运算就可以决定的过程。”有意思的是，从希尔伯特对这个问题的陈述中可以看出，他明确地要求设计一个算法。因此，他显然是假设这样的算法存在，人们所要做的只是找到它。现在我们知道，这个任务是无法完成的，即它是算法上不可解的。但对那个时期的数学家来说，以他们对算法的直观认

算法分析导论（第2版）

识，得出这样的结论是不可能的。非形式地说，算法是为实现某个任务而构造的简单指令集。用日常用语来说，算法又被称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学文献中就包含执行各种各样计算任务的算法描述。例如，我国古代数学经典《九章算术》中就记述了包括求最大公约数、最小公倍数、开平方根、开立方根等在内的诸多算法。虽然算法在数学中已有很长的历史，但在20世纪之前，算法本身一直没有精确的定义。数学家们面对希尔伯特的第10个问题显得束手无策。由于缺乏对算法本身的精确定义，所以要证明某个特定任务不存在算法就更不可能了。要想破解希尔伯特的第10个问题，人们不得不等待算法的精确定义的出现。直到1936年，曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中之应用》的论文。该文最终于1937年正式发表，并立即引起了广泛关注。在论文中，图灵描述了一种可以辅助数学研究的机器，也就是后来被称为“图灵机”的抽象系统。与此同时，另外一位数学家阿隆佐·丘奇（AlonzoChurch）也独立地提出了另外一套系统，即所谓的Lambda演算。图灵采用他的图灵机来定义算法，而丘奇则采用Lambda演算来定义算法，后来图灵证明这两个定义是等价的。由此，人们在算法的非形式概念和精确定义之间建立了联系，即算法的直觉概念等价于图灵机，这就是所谓的“丘奇－图灵”论题。“丘奇－图灵”论题提出的算法定义是解决希尔伯特第10个问题所需的。而第10个问题的真正解决则要等到1970年，借助于丘奇与图灵的杰出贡献，马提亚塞维齐（YuriMatiyasevich）在戴维斯（MartinDavis）、普特纳姆（HilaryPutnam）和罗宾逊（JuliaRobinson）等人工作的基础上，最终证明检查多项式是否有整数根的算法是不存在的。上述四人的名字也紧紧地同希尔伯特的第10个问题联系在了一起。破解希尔伯特的第10个问题的过程更像一场声势浩大又旷日持久的国际协作和学术接力。每个人的工作都必不可少，而且大家都感觉已经相当接近问题的最终答案。后来的历史见证了马提亚塞维齐敏锐地接过最后一棒并完成终点冲刺的伟大一幕。更有意思的是，彼时正值美苏冷战最为紧张的时期，两个超级大国之间的正常学术交流几乎完全中断。但这或许就是科学无国界的一个重要体现，尽管国家层面上双方剑拔弩张，而科学家在私下仍然以一种惺惺相惜的默契方式彼此神交。特别是在得知苏联数学家完成了最终的证明时，美国同行都表现得相当振奋和由衷的喜悦，这不得不说是学术界的一段佳话。回顾建立算法形式化定义和破解希尔伯特之第10个问题的那段风起云涌的历史，我们不得不由衷地感叹：算法对于我们的世界是多么重要。可以这样说，自计算机科学诞生之日起，关于算法的研究就一直是一个核心话题。现代计算机科学中充满了各种各样的算法，

译者序V

许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如，提出单源最短路径算法的迪可斯特朗（EdsgerDijkstra）①、提出字符串匹配算法的高德纳（DonaldKnuth）②、提出多源最短路径算法的弗洛伊德（RobertFloyd）③，以及提出快速排序算法的霍尔（AntonyHoare）④等。其中，高德纳是最年轻的图灵奖得主这一纪录的保持者（获奖时年仅36岁），并以计算机算法设计与分析领域的经典巨著《计算机程序设计艺术》而广为人知。

作为导师，高德纳一生共指导过28位博士生，而《算法分析导论（第2版）》作者之一的罗伯特·塞奇威克（RobertSedgewick）便是其中之一。塞奇威克曾经是普林斯顿大学计算机科学系的创立者暨

首任系主任，他同时还是著名的Adobe公司的董事。作为一位世界知名的计算机科学家，

塞奇威克于1997年当选ACM（AssociationforComputingMachinery，国际计算机学会）院

士，并因从“对称二叉树”中导出了红黑树而享誉计算机界。

塞奇威克与费利佩·弗拉若莱（PhilippeFlajolet）曾合作撰写过数本算法分析领域的著作，《算法分析导论（第2版）》即为其中一部在全世界范围内广泛流传的经典之作。弗拉若莱是一名法国计算机科学家，法国科学院院士，同时也被称为“分析组合学之父”。他与合作者共同提出的Flajolet-Martin算法更是当今互联网与大数据时代背景下，网站分析统计的重要基石。

然而，天妒英才，2011年3月，休假期间的塞奇威克惊悉多年的老友弗拉若莱突然离世。悲痛万分的塞奇威克怀着对逝者的无限缅怀写了感人至深的悼词：“弗拉若莱的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者，他们可再续他的数学梦想。”在这样的背景下，塞奇威克以极大的热情投入工作，历经数百个日夜，终于在2012年10月将《算法分析导论（第2版）》的第2版付梓。塞奇威克坚信弗拉若莱的精神会在后来人的工作中得到永生，进而希冀《算法分析导论（第2版）》读者能够循着弗拉若莱的脚步，继续追求他的数学梦想。

《算法分析导论（第2版）》全面系统地介绍了算法分析中需要使用的基本技术，所涉及的内容既来自包括离散数学、组合数学、概率论等在内的经典数学问题，也有来自算法及数据结构等计算机科学问题。像递归、母函数、树形结构、字符串、映射以及散列等算法分析话题均有讨论。可以说《算法分析导论（第2版）》是一本研究算法分析的权威之作。

作为译者，我们希望自图灵以来的算法研究能够在更宽阔的范围内，被更光大地发扬，尤其希望中国的计算机科研人员能够从《算法分析导论（第2版）》中找到启迪研究工作的智慧。同时，也希望通过《算法分析导论（第2版）》向神交已久的两位大师——弗拉若莱和塞奇威克送上最崇高的敬意。

①1972年图灵奖得主。

②1974年图灵奖得主。

③1978年图灵奖得主。

④1980年图灵奖得主。

算法分析导论（第2版）

最后，《算法分析导论（第2版）》翻译工作的完成有赖于数位合作者的倾心付出，其中常青翻译了《算法分析导论（第2版）》的第1至6章、左飞翻译了第8、9章、于佳平翻译了第7章。其他参与《算法分析导论（第2版）》翻译和校对工作的人员还有李振坡、邵臣、叶剑、赵冰冰、贾啸天、钱文秀、丁星芸、李晓华、黄帅。自知论道须思量，几度无眠一文章。因时间和水平有限，纰漏与不足之处在所难免，译者恳切地期望广大同行及读者朋友不吝批评斧正。

序

分析算法可以给人带来两方面的快乐。其一，人们可以尽享优雅计算过程中所蕴含的让人沉醉的数学模式；其二，我们所学到的理论知识可以让自己更好更快地完成工作，这无疑是最实际的好处。

尽管数学模型只是对真实世界的一种理想化近似，但它对所有的科学活动而言都可谓是一剂灵丹妙药。在计算机科学中，数学模型往往可以精确地描述计算机程序所创造的世界，数学模型的重要性也因此大大增加了。我想，这也是为什么我在读研究生时会沉迷于算法分析，以至于这成为我迄今为止的主要工作。

但直到今天，算法分析在很大程度上还是局限在相关专业的研究生和科研人员的圈子里。算法分析的概念既不晦涩也不复杂，但确实比较新，所以相关概念的学习和使用都还需要一些时间才能成熟。

现在，经过40余年的发展，算法分析已经非常成熟，足以成为计算机专业标准课程中的一部分。Sedgewick和Flajolet写的这本众人翘首以盼的教科书也因此备受欢迎。《算法分析导论（第2版）》的作者不仅仅是这个领域的世界级专家，同时也是算法分析的布道大师。我坚信，这《算法分析导论（第2版）》会让每一位细细品读的计算机研究人员从中获益。

D.E.Knuth

前言

《算法分析导论（第2版）》的主要目的是介绍算法的数学分析中涉及的主要技术。涵盖的内容都来自经典的数学和计算科学领域，包括来自数学领域的离散数学、实分析基础和组合数学，来自计算机领域的算法和数据结构等。《算法分析导论（第2版）》的重点是“平均情况”或是“概率性”的分析，对“最差情况”或“复杂度”分析所需的基本数学工具也有所涉及。

我们假设读者对计算机科学和实分析的基本概念是比较熟悉的。简单来说，读者要能够编写程序和证明定理