分析算法的人享有双重的幸福。首先，他们能够体验到优雅数学模式纯粹的美，这种模式存在于优美的计算过程之中；其次，当他们的理论使得其他工作能够做得更快、更经济时，他们能够得到实际的褒奖。本书作者是算法分析领域的世界级领袖，这部著作我们也是期盼已久了。－－Donald E. Knuth
本书全面介绍了算法的数学分析中使用的基本方法，所涉及的内容来自经典的数学课题 (包括离散数学、初等实分析、组合数学)，以及经典的计算机科学课题 (包括算法和数据结构) 。虽然书中论述了“最坏情形”和“复杂性”分析所需的基本数学工具，但是重点还是讨论“平均情形”或“概率”分析。论题涉及递归、生成函数、渐近性、树、串、映射等内容，以及对排序、树查找、串查找和散列诸算法的分析。
尽管人们极为关注算法的数学分析，但是关于普遍使用的方法和模型方面的基本信息尚不能为该领域的学生和研究人员直接使用。作者在本书中处理这种需求，把该领域出现的挑战以及为迎接这些挑战所必需的背景资料完美地结合在一起。
无
本书是对算法数学分析中主要方法的综述。所涉及的材料来自经典的数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构。重点在于“平均情形”或“概率”分析，不过，也包括“最坏情形”和“复杂性”分析所需要的基本数学工具。
我们假设读者熟悉计算机科学和实分析中的基本概念。概括地说，读者应该既能编写程序，又能够证明定理；在其他方面，本书是自包容的。书中还在文献里提供了丰富的预备性材料。我们计划中的本书姐妹篇将讨论更为先进的方法。这两部著作总共涵盖那些主要的方法和技巧，并提供通向算法分析日益增长的文献的捷径。
本书计划作为算法数学分析初级和高级课程的教科书。它也可以在计算机科学的离散数学课程中使用，因为它包含了离散数学和组合数学中的基本方法以及计算机科学学生所熟悉的重要离散结构的基本性质。传统上，在这些课程中知识范围要广一些，但是许多教师可能发现这里的做法是使学生从事实质性部分学习的有用方式。本书还可以作为数学和应用数学的学生了解与算法和数据结构相关的计算机科学原理的教材。
辅以文献中论文的补充，本书可作为研究生算法分析导论性课程的基础来使用，或作为那些想要接近该领域文献的数学或计算机科学研究人员的参考书或自学基础材料。它还可以作为应用和方法的资源为字符组合数学和离散数学的学生和研究人员使用。
尽管算法数学分析方面的文献很多，但是关于普遍使用的方法和模型方面的基本信息尚不能很容易地为该领域的学生和研究人员直接使用。本书的目的就是处理这种情况，把想要提供给读者该领域问题的正确评价和学习正在发展以满足这些挑战的高级工具的需求背景的大量材料汇聚在一起。
背景要求。假设数学程度为在大学学习一年或两年的水平。组合数学和离散数学的基本课程可以提供有用的背景知识（可能与本书的某些内容重叠），实分析、数值方法或初等数论中的课程也是如此。我们将涉及所有这些领域，不过在这里只综述必需的材料，那些想要知道更多信息的读者可以参考标准的教科书。
假设编程经验为在大学学习过一个或两个学期的水平，包括初等数据结构。我们不在编程和算法实现问题上过多地耗费精力，算法和数据结构则是我们研究的中心课题。从某种意义上讲，我们的处理是完善的：对于基本的信息，我们给出概要的总结，必要时可以参考标准的教科书和一些基本的原始资料。
强烈推荐读者在数学计算时使用诸如MAPLE或Mathematica这样的计算机软件。当验证本书中的材料或求解习题结果时，这些软件系统可以帮助摆脱烦琐的计算。
相关的书籍。相关的教科书包括Knuth的The Art of Computer Programming；Gonnet和Baeza-Yates的Handbook of Algorithms and Data Structure；Sedgewick的Algorithms；Graham、Knuth和Patashnik的Concrete Mathematics；Cormen、Leiserson和Rivest的Introduction to Algorithms。本书可以看作是对这些著作的增补，下面依次评述。
实质上，本书最接近于Knuth的开创性著作。不过，我们的重点是在分析的数学方法上，而Knuth著作的范围广而全，算法的性质起着主要的作用，而分析的方法则是第二位的。本书可以作为Knuth的著作中所论及的先进结果的基础准备。
我们还讨论了自从Knuth的书出版以来始终在发展的算法分析中的方法和结果。Gonnet和Baeza-Yates的著作是这些结果的透彻综述，包括全面的参考文献；它主要介绍源自文献的一些相关结果。本书提供了通向该文献的基本预备内容。
我们也努力把重点放在基础、重要和有趣的算法上，像Sedgewick的Algorithms中所描述的一些算法，而Graham、Knuth和Patashnik的Concrete Mathematics则几乎全部侧重在数学方法方面。我们想要使本书成为Graham、Knuth和Patashnik的书中所讨论的基本数学方法和Sedgewick的书所涉及的基本算法的桥梁。
Cormen、Leiserson和Rivest的Introduction to Algorithms是那些提供通向算法的“设计和分析”研究文献著作的代表，一般是基于方法性能的粗略的最坏情形估计的。当需要更精确的结果时（对于大多数重要的方法），更复杂的模型和数学工具是必不可少的。Cormen、Leiserson和Rivest把重点放在算法的设计（通常带有为最坏情形性能定界的目的）上，而解析结果则用于帮助指导算法的设计。另一方面，我们的书是对他们的书以及类似的书的补充，因为我们侧重于算法的分析，特别是对那些能够用于获取可以预报算法性能的详细结果的方法。在这个过程中，我们也考虑与各种经典数学工具的关系，第1章全部用来描述这种环境。
本书还为其姐妹篇Analytic Combinatorics奠定了基础，那本书以更广的视野对本书涉及的材料进行一般的处理，并开发了高级方法和模型，这些方法和模型不仅在算法平均情形的分析中，而且在组合数学中，均可作为新的研究基础。对于阅读那本姐妹篇，需要更高水平的数学基础，相当于高年级本科生或低年级研究生所应具备的水平。当然，认真学习本书也足以具备这些基础。毫无疑问，使得本书充分有趣始终是我们的目的，读者将会惊喜地发现本书涉及更先进的材料。
如何使用本书。本书的读者在离散数学和计算机科学方面的基础很可能有相当大的差异。因此，了解书中的基本结构很有必要：全书总共八章，先是导论性的一章，接着的三章侧重于数学方法，最后四章集中讨论算法分析的应用：
引论
1. 算法分析概述
离散数学方法
2. 递归关系
3. 生成函数
4. 渐近逼近
算法与组合结构
5. 树
6. 排列
7. 串与trie树
8. 字与映射
第1章将书中材料恰当地进行概括，并帮助所有读者理解本书的基本目标以及其余各章在满足这些目标方面所担当的角色。第2章至第4章更侧重于数学，涉及离散数学的一些方法，主要讨论一些基本概念和方法。第5章到第8章侧重于计算机科学，包含组合结构的一些性质，与基本算法的关系，以及若干解析结果。
虽然本书是自完备的，但是根据教师经验和学生的基础，可以有所侧重。一种方法是更偏重于数学，重点讲解本书前半部分的定理和证明，并介绍第5章到第8章的应用。另一种方法是更偏重于计算机科学，扼要地讨论第2章到第4章中的主要数学工具，而着重讨论本书第二部分的算法题材。不过，我们主要的意图是大部分的学生通过细心地通读本书，能够同时学到数学和计算机科学两个领域中新的东西。
具有较强计算机科学基础的学生可能已经见过本书后半部分的许多算法和数据结构，但在开始的时候他们的数学知识并不多；具有较强数学背景的学生很可能发现数学材料很熟悉，但算法和数据结构或许有些生疏。包括本书所有内容的课程可以帮助这两类学生根据他们已有的知识来填补知识缺口。
在每章末尾列出的参考文献以及散布在文中的数百道习题是对教材的补充，它们将鼓励读者更深刻地考虑书中的内容并考查原始的资料。
我们教授本书的经验已经证明，教师能够经常通过基于计算的实验课和家庭作业来补充讲义和阅读材料。这里所涵盖的内容对于学生使用诸如Mathematica或MAPLE这样的符号处理系统来深入研习专门知识是一个理想的构架。通过与经验研究比较而使数学研究得以确认的经验对于许多学生而言可能是非常有价值的。
致谢。我们非常感谢INRIA、普林斯顿大学和国家科学基金会，他们对本书提供了主要的支持。其他的支持由布朗大学、European Community（Alcom Project）、Institute for Defence Analyses、Minist弐e de la Recherche et de la Technologie、斯坦福大学、Universit* Libre de Bruxelles以及Xerox Palo Alto Research Center提供。本书耗费多年时间撰著，因此提供支持的个人和组织的名单很长，在此不能一一列出，深为抱歉。
Don Knuth对我们工作的影响极为重要，这从教材中明显可以看出。
普林斯顿、巴黎以及普罗维登斯大学的学生们这些年来对利用这些材料的早期版本授课的课程回馈了有益的信息。我们还要感谢Philippe Dumas、Mordecai Golin和他的学生San Kuen Chan、Ka Po Lam、Ngok Hing Leung、Derek Ka-Cheong Lueng和King Shan Lui，以及三位不具名评论家对手稿的详细评论。
R. S.
Ph. F.
1995年9月，Corfu
无
分析算法的人享有双重的幸福。首先，他们能够体验到优雅数学模式纯粹的美，这种模式存在于优美的计算过程之中。其次，当他们的理论使得其他工作能够做得更快、更经济时，他们能够得到实际的褒奖。
数学模型始终是所有科学活动至关重要的灵感，尽管它们只是真实世界现象的近似理想化。在计算机内部，这种模型比以前更优美，因为计算机程序创建了人造世界。在这样的世界中，数学模型常常得以精确地使用。我想，这就是为什么当我还是研究生时就沉迷于算法分析，以及为什么这个课题迄今为止始终是我一生主要工作的原因。
然而，直到最近，算法分析在很大程度上依然是研究生和研究人员的禁区。它的概念确实不深奥也不困难，但是它们相对新颖，因此，挑选出学习它们和使用它们的最佳方法需要时间。
如今，经过30多年的发展，算法分析已经成熟到这样一种程度，即它已经为其在标准的计算机课程中占有一席之地做好了准备。因此，我们期盼已久的这部Sedgewick和Flajolet的著作极受欢迎。本书作者不仅是这个领域在世界范围内的领袖，而且还是理论阐述的大师。我敢肯定，每一位严肃的计算机科学家都将发现本书在许多方面颇富启迪性。
D. E. Knuth
（美）Robert Sedgewick, （法）Philippe Flajolet：（美）Robert Sedgewick: 拥有斯坦福大学博士学位 (导师为Donald E. Knuth) ，普林斯顿大学计算机科学系教授，Adobe Systems公司董事，曾是Xerox PARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。除本书外，他还与Philippe Flajolet合著了《算法分析导论》一书。
（法）Philippe Flajolet: INRIA的高级研究主任，在Ecole Polytechnique和普林斯顿大学任教，并在斯坦福大学、智利大学和弗吉尼亚技术大学拥有访问席位。他还是法国科学院的通信会员。
冯舜玺 李学武 裴伟东 等：暂无简介
算法分析一般包括两种不同的方法。第一种方法研究确定最坏情形的性能，有时称之为计算复杂性。当面对一种新的算法时，算法分析能粗略地分析：新算法能够有多好？它比其他算法性能大致好多少？就算法分析来说，这种复杂性分析由于抛弃一些次要因素而丧失不少的精度，它提供不了算法具体实现的性能特征以及与其他算法具体比较所需要的足够信息。不过，我们可以把它看成是形成更精练、更准确分析过程的第一步。第二种方法通过确定最佳情形、最坏情形以及平均情形的性能来精确地刻画算法的性能，在需要的时候，能够通过可以精化的方法准确地预测特定算法的性能特征，其中最常见的是对时间和空间这样一些基本资源的消耗，尤其是时间。算法分析表示整个分析过程，它提供任意精度的解决方案。
本书是对算法的数学分析中主要方法的综述，涉及离散数学、数学分析、组合数学以及数据结构和算法。由于重点在于平均情形的分析，因此必然要涉及模型、分布、矩阵以及概率论和数理统计中的其他内容。
经过近几十年的发展，算法分析已经十分成熟，能够在标准的计算机课程中占有一席之地，本书为那些徘徊在该领域之外却苦于不得其门而入的新手指出通往研究之门的捷径。为本科生开设这门课程可以有少数内容现用现补，研究生在先修有关数学和计算机的相应知识的基础上，可以将本书用于算法分析的导论性课程。数学和计算机领域中不同专业的学生，选修本书可以各有侧重，作者在前言中提出了指导性的建议。
本书语言简炼，推导紧凑，能够很好地锻炼我们的独立阅读能力。在验证书中的结论和求解练习的结果时，若能使用像Matlab、Mathematica或MAPLE这样的计算机软件，则可帮助我们摆脱繁琐的演算，节省宝贵的时间。
本书的另一大特点是课文中以及各章末尾所列出的参考文献，对于有心深造的读者，这是十分宝贵的财富。
全书共有8章内容。第3章由李学武翻译，第4章、第6章、第7章和第8章由裴伟东翻译，其余工作由冯舜玺完成。因时间和水平所限，译文难免存在一定的问题，恳切期望广大读者批评指正。
译 者
2006年3月
无
第1章 算法分析概述 1
1.1 为什么要对算法进行分析 1
1.2 计算复杂性 2
1.3 算法分析的过程 6
1.4 平均情形分析 7
1.5 例：快速排序的分析 8
1.6 渐近逼近 13
1.7 分布 14
1.8 概率算法 16
参考文献 18
第2章 递归关系 21
2.1 基本性质 22
2.2 一阶递归 24
2.3 非线性一阶递归 26
2.4 高阶递归 28
2.5 求解递归的方法 32
2.6 二分分治递归和二进制数 37
2.7 一般的分治递归 43
参考文献 48
第3章 生成函数 51
3.1 常规生成函数 51
3.2 指数生成函数 55
3.3 利用生成函数求解递归 57
3.4 生成函数的展开 63
3.5 利用生成函数进行变换 65
3.6 关于生成函数的函数方程 67
3.7 利用OGF求解三数中值Quicksort递归 69
3.8 利用生成函数的计数 71
3.9 符号方法 74
3.10 拉格朗日反演 80
3.11 概率生成函数 82
3.12 二元生成函数 84
3.13 特殊函数 91
参考文献 94
第4章 渐近逼近 97
4.1 有关渐近逼近的记号 98
4.2 渐近展开式 102
4.3 渐近展开式的操作 107
4.4 有限和的渐近逼近 112
4.5 欧拉-麦克劳林求和 114
4.6 二元渐近性 119
4.7 拉普拉斯方法 128
4.8 算法分析中的“正态”例 131
4.9 算法分析中的“泊松”例 135
4.10 生成函数的渐近性 136
参考文献 140
第5章 树 141
5.1 二叉树 141
5.2 树和森林 143
5.3 树的性质 145
5.4 树的算法 147
5.5 二叉查找树 150
5.6 Catalan树中的平均路径长 153
5.7 二叉查找树中的路径长 156
5.8 随机树的可加参数 159
5.9 高 162
5.10 树性质平均情形结果的小结 167
5.11 树和二叉树的表示 168
5.12 无序树 172
5.13 标号树 178
5.14 其他类型的树 180
参考文献 186
第6章 排列 189
6.1 排列的基本性质 190
6.2 排列的算法 194
6.3 排列的表示法 196
6.4 计数问题 200
6.5 利用CGF分析排列的性质 204
6.6 逆序与插入排序 211
6.7 左向右最小值与选择排序 216
6.8 圈与原位排列 220
6.9 极值参数 223
参考文献 226
第7章 串与trie树 229
7.1 串查找 230
7.2 位串的组合性质 232
7.3 规则表达式 239
7.4 有限状态自动机与Knuth-Morris-Pratt算法 242
7.5 上下文无关语法 244
7.6 trie树 248
7.7 trie算法 251
7.8 trie树的组合性质 254
7.9 更大的字母表 258
参考文献 259
第8章 字与映射 263
8.1 使用分离链接的散列 263
8.2 字的基本性质 265
8.3 生日悖论与赠券收藏家问题 269
8.4 占有约束与极值参数 274
8.5 占有分布 278
8.6 开放定址散列法 284
8.7 映射 289
8.8 整数因子分解与映射 297
参考文献 301
索引 303
