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

序 分析算法可以给人带来两方面的快乐。其一，人们可以尽享优雅计算过 程中所蕴含的让人沉醉的数学模式；其二，他们所学得的理论知识可以让自 己更好更快地完成工作, 这无疑是最实际的好处。 尽管数学模型只是对真实世界的一种理想化近似，但它对所有的科学活 动而言都可谓是一剂灵丹妙药。在计算机中，数学模型往往可以精确地描述 计算机程序所创造的世界，我想数学模型的重要性也因此大大增加了。我想， 这也是为什么我在读研究生时会沉迷于算法分析，以至于这成为了我迄今为 止的主要工作。 但直到今天，算法分析在很大程度上还是局限在相关专业的研究生和科 研人员的圈子里。算法分析的概念既不晦涩也不复杂，但确实比较新，所以 相关概念的学习和使用都还需要一些时间才能成熟。 现在，经过40 余年的发展，算法分析已经非常成熟，足以成为计算机专 业标准课程中的一部分。Sedgewick 和Flajolet 写的这本众人翘首以盼的教科 书也因此备受欢迎。本书的作者不仅仅是这个领域的世界级专家，同时也是 算法分析的布道大师。我坚信，这本书会让每一位细细品读的计算机研究人 员从中获益。 D. E. Knuth 前 言 本书的主要目的是介绍算法数学分析中涉及的主要技术。涵盖的内容都 来自经典的数学和计算科学领域，包括来自数学领域的离散数学、实分析基 础和组合数学，来自计算机领域的算法和数据结构等。本书的重点是“平均 情况”或是“概率性”的分析，对“最差情况”或“复杂性”分析所需的基 本数学工具也会涉及。 我们假设读者对计算机科学和实分析的基本概念是比较熟悉的。简单来 说，读者要能够编写程序和证明定理。除此之外，本书对读者没有其他要求。 本书主要是为了用作高阶算法分析课程的教科书。书中涵盖了计算机专 业学生所需离散数据的基本技术、组合数学和重要离散结构的基本属性，因 此也可以用在计算机专业的离散数学课程中。通常此类课程所涵盖的内容都 比较广泛，但很多教师都用自己的方法来选取其中的一部分内容教给学生。 本书还可以用于给数学和应用数学的学生介绍计算机科学中与算法和数据结 构有关的基本原则。 关于算法的数学分析的论文非常多，但这个领域的学生和研究人员却很 难学习到该领域中广泛使用的方法和模型。本书的目标就是解决这个问题， 一方面要让读者知道这个领域所面临的挑战，另一方面要让读者有足够的背 景支持来学习为应对这些挑战而正在开发的工具。我们列出了相关的参考文 献，因此本书可以作为研究生算法分析入门课程的基础教材，也可以用作想 学习该领域中相关文献的数学或计算机领域研究人员的参考资料。 准备工作。假设读者有大学一二年级或与之等同的数学基础。组合数学 和离散数学方面的基本课程，以及实分析、数值方法和基本数论方面的课程， 有助于理解本书（有些内容跟本书是交叉的）。本书将涉及这些领域，但我们 在这里只会对必要的内容做介绍。我们也会列出参考文献供想进一步学习的 人参考。 读者需要一到两个学期大学水平的编程经验，包括了解基本数据结构。 我们不会涉及编程和具体实现的问题，但算法和数据结构是我们的核心。同 数学方面的基础知识一样，本书中我们会简要介绍基本的信息，同时列出标 准教材和知识来源供读者参考。 相关书籍。与本书有关的书籍包括D. E. Knuth 写的Art of Computer Programming（《计算机程序设计艺术》），Sedgewick 和Wayne 写的Algorithms, Fourth Edition（《算法》第4 版），Cormen、Leiserson、Rivest 和Stein 写 的Introduction to Algorithms（《算法导论》），以及我们自己写的Analytic Combinatorics（《分析组合论》）。本书可以作为这些书的补充材料。 从基本思路上来说，本书与D. E. Knuth 的书是最相似的。但这本书的重 点是算法分析中的数学技术，而D. E. Knuth 的那些书是内容更丰富的百科全 书，其中算法的各种性质是主角，算法分析方法只是配角。本书可以作为学习D. E. Knuth 书中进阶内容的基础。这本书还涵盖了D. E. Knuth 的书诞生之后在 算法分析领域出现的新方法和新结果。 本书尽可能地涵盖各种重要、有趣的基础算法，例如，Sedgewick 的《算法》 （现在是第4 版了，跟K. Wayne 合著的）中所介绍的那些算法。《算法》一书 涵盖了经典的排序、搜索和用于处理图和字符串的算法。我们这本书的重点 是介绍用于预测算法性能和比较算法性能优劣的数学知识。 Cormen、Leiserson、Rivest 和Stein 合著的《算法导论》是算法方面的标 准教材，其中提供了关于算法设计的各种文献。《算法导论》一书（及相关 的文献）关注的是算法设计和理论，大部分是基于最差性能边界的。而本书 关注的则是算法分析，尤其是各种科学研究（而不是理论研究）所需的技术。 第1 章就是为此做铺垫的。 本书还会介绍分析组合学，它可以让读者开阔视野，也有助于开发用于 新研究的高级方法和模型，而且不局限于算法分析，它还可以用于组合学和 更广泛的科学应用。那一卷对读者的数学水平要求要高一些，差不多需要本 科高年级学生或研究生一年级的水平。当然，仔细阅读本书也有助于读者学 习相关的数学知识。我的目标是尽可能让读者感兴趣，有动力更深入地学习。 如何使用这本书。本书读者在数学和计算机科学方面的知识储备肯定是 不一样的。所以，读者要注意本书的结构：全书共9 章，第1 章是导论，第 2~5 章介绍数学方法，最后4 章是组合结构及其在算法分析中的应用，具体 如下： 导论 第1 章 算法分析 离散数学方法 第2 章 递归关系 第3 章 生成函数 第4 章 渐近逼近 第5 章 分析组合学 算法与组合结构 第6 章 树 第7 章 排列 第8 章 串和trie 树 第9 章 字与映射 第1 章会介绍全书的主要内容，帮助读者理解本书的基本目标以及其余 各章的目的。第2~4 章涵盖了经典离散数学中的方法，重点是基本概念和技 术。第5 章是一个转折点，其中涵盖了分析组合学。计算机和计算模型的出 现带来了很多新问题，这些问题往往涉及大型的离散结构。分析组合学的内 容就是研究这些离散结构以解决新出现的问题。第6~9 章则回到了计算机科 学，涵盖各种组合结构的属性，它们跟基本算法的关系，以及分析结果。 我们试图让本书是自包含的，但本书的组织结构可以让老师很方便地根 据学生和老师自己的背景知识及经验选取要重点讲解的部分。一种比较偏数 学的教学方案是重点讲解本书第一部分的理论和证明，然后过渡到第6~9 章 的相关应用。另一个比较偏计算机科学的方案是简要介绍第2~5 章的数学工 具，重点放在本书第二部分跟算法有关的内容。但我们的根本目标还是要让 绝大部分的学生能通过本书学习到数学和计算机科学的新知识。 本书还罗列了很多参考资料以及数百个练习，鼓励读者去研究原始材料， 更深入地研究本书中的内容。根据我们的教学经验，讲师可以通过计算实验 室和家庭作业，灵活地组织授课和阅读材料。本书的内容为学生深入学习诸 如Mathematica、MAPLE或SAGE之类的符号计算系统提供了一个很好的框架。 更重要的是，对学生而言，通过比较数学研究结果和实际测试结果得出的结 论是有重要价值的，不可忽略。 配套网站。本书的一个重要特点就是拥有配套的网站aofa.cs.princeton. edu。这个网站是免费的，提供了很多关于算法分析的补充材料，包括课件和 相关网站的链接，其中有一些关于算法和分析组合学的网站。这些材料对讲 授这些内容的教师和自学者都很有帮助。 致谢。我们非常感谢普林斯顿大学的INRIA 和国家科学基金，它们是我 们这本书的主要资助者。其他的资助来自布朗大学、欧共体（Alcom 项目）、 国防分析研究院、法国研究与技术部、斯坦福大学、布鲁塞尔自由大学和施 乐帕克研究中心。本书历时多年才得以付梓，在此不可能一一列出诸多为本 书提供支持和帮助的人和机构，我们对此深表歉意。 正如书中所说，D. E. Knuth 对本书有重要的影响。 过去几年，在普林斯顿、巴黎和普罗维登斯听过我课的学生们为本书提 供了宝贵的反馈意见。全世界各地的学生和教师也为本书的第1 版提出了 很多好建议。我们在此特别感谢Philippe Dumas、Mordecai Golin、Helmut Prodinger、Michele Soria、Mark Daniel Ward 和Mark Wilson 的帮助。 Ph. F. 和R. S. 1995 年9 月于科孚岛 R. S. 2012 年12 月于巴黎 第2 版声明 2011 年3 月，我和我的妻子Linda 去了一个美丽而遥远的地方旅行，因 此有几天没上网。当我找到机会处理邮件时，却得到一个让人震惊的消息： 我的挚友和同事Philippe 突然去世了。由于无法及时赶到巴黎参加葬礼， Linda 和我为我们的好朋友写了悼词，在此分享给本书的读者，让我们一起缅 怀我们的这位朋友。 悲痛万分，我在一个遥远的地方缅怀我长期以来的好友和同事 Philippe Flajolet。很遗憾不能亲自参加葬礼，但我坚信，将来一定有 很多机会来缅怀Philippe，希望到时我能参与。 Philippe 才华横溢、匠心独运、求知若渴、不知疲倦，同时慷慨 大方、乐善好施，他的生活方式深深地感染了我。他改变了很多人 的生活，包括我自己的。随着我们的诸多研究论文变成综述，进而 发展成若干篇章，第一本书，第二本书，最终写书成为了我们一生 的工作——在跟Philippe 携手同行时，我与全世界很多学生和合作 者都感受到了Philippe 的真诚和友好。我们曾在全世界各个地方的 咖啡馆、酒吧、午餐室或客厅里一起工作。无论何处，Philippe 的 工作方式始终不变。我们会先聊聊某个朋友的趣事，然后开始工作。 一个眼神的交流，真诚的笑声，抽两根烟，喝两口啤酒，咬两口牛排， 吃点薯条，然后听到一声“好……”，我们就这样解决一个又一个问题， 证明一条又一条定理。对很多与他合作过的人而言，这些时刻都铭 记心中。 这个世界又少了一个聪明高效的数学家。Philippe 的离世意味着 很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承 者，继续追寻他的数学梦想。我们会在会议上为他举杯，我们会以 他的研究成果为基础继续前进，我们的论文会加上一句铭文“谨以 此纪念Philippe Flajolet”，我们会将此一代代传承下去。亲爱的朋友， 我们非常想念你，我坚信，你的精神会在我们的工作中得到永生。 我们合著的《算法分析导论》一书的第2 版就是这样完成的。谨以此书 纪念Philippe Flajolet，也希望更多的人通过这本书继续追寻Philippe 的数学梦 想。 R. S. 2012 年10 月于罗得岛州詹姆斯敦

TABLE OF CONTENTS CHAPTER ONE: ANALYSIS OF ALGORITHMS 3 1.1 Why Analyze an Algorithm? 3 1.2 ＆#1048891;eory of Algorithms 6 1.3 Analysis of Algorithms 13 1.4 Average-Case Analysis 16 1.5 Example: Analysis of Quicksort 18 1.6 Asymptotic Approximations 27 1.7 Distributions 30 1.8 Randomized Algorithms 33 CHAPTER TWO: RECURRENCE RELATIONS 41 2.1 Basic Properties 43 2.2 First-Order Recurrences 48 2.3 Nonlinear First-Order Recurrences 52 2.4 Higher-Order Recurrences 55 2.5 Methods for Solving Recurrences 61 2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers 70 2.7 General Divide-and-Conquer Recurrences 80 CHAPTER THERE: GENERATING FUNCTIONS 91 3.1 Ordinary Generating Functions 92 3.2 Exponential Generating Functions 97 3.3 Generating Function Solution of Recurrences 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-＆#1048891;ree Recurrence with OGFs 120 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 CHAPTER FOUR: ASYMPTOTIC APPROXIMATIONS 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8 “Normal” Examples from the Analysis of Algorithms 207 4.9 “Poisson” Examples from the Analysis of Algorithms 211 CHAPTER FIVE: ANALYTIC COMBINATORICS 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 CHAPTER SIX: TREES 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 CHAPTER SEVEN: PERMUTATIONS 345 7.1 Basic Properties of Permutations 347 7.2 Algorithms on Permutations 355 7.3 Representations of Permutations 358 7.4 Enumeration Problems 366 7.5 Analyzing Properties of Permutations with CGFs 372 7.6 Inversions and Insertion Sorts 384 7.7 Left-to-Right Minima and Selection Sort 393 7.8 Cycles and In Situ Permutation 401 7.9 Extremal Parameters 406 CHAPTER EIGHT: STRINGS AND TRIES 415 8.1 String Searching 416 8.2 Combinatorial Properties of Bitstrings 420 8.3 Regular Expressions 432 8.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm 437 8.5 Context-Free Grammars 441 8.6 Tries 448 8.7 Trie Algorithms 453 8.8 Combinatorial Properties of Tries 459 8.9 Larger Alphabets 465 CHAPTER NINE: WORDS AND MAPPINGS 473 9.1 Hashing with Separate Chaining 474 9.2 The Balls-and-Urns Model and Properties of ＆Words 476 9.3 Birthday Paradox and Coupon Collector Problem 485 9.4 Occupancy Restrictions and Extremal Parameters 495 9.5 Occupancy Distributions 501 9.6 Open Addressing Hashing 509 9.7 Mappings 519 9.8 Integer Factorization and Mappings 532 List of ＆#1048891;eorems 543 List of Tables 545 List of Figures 547 Index 551