前言

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

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

本书主要用作高阶算法分析课程的教科书。书中涵盖了计算机专业学生所需离散数学的基本技术、组合学和重要离散结构的基本属性等内容，因此本书也可以用在计算机专业的离散数学课程中。通常此类课程所涵盖的内容都比较广泛，很多教师会用自己的方法来选取其中的一部分内容教给学生，因此本书还可以用于给数学和应用数学专业的学生介绍计算机科学中与算法和数据结构有关的基本原理。

关于算法的数学分析的论文非常多，但这个领域的学生和研究人员却很难学习到该领域中广泛使用的方法和模型。本书的目标就是解决这个问题，一方面要让读者知道这个领域所面临的挑战，另一方面要让读者有足够的背景支持来学习为应对这些挑战而正在开发的工具。我们列出了相关的参考资料，因此本书可以作为研究生算法分析入门课程的基础教材，也可以用作想学习该领域中相关资料的数学和计算机科学领域研究人员的参考资料。

准备工作

如读者有大学一二年级或与之同等的数学基础，学习过组合学和离散数学，以及实分析、数值方法和基本数论方面的课程，将有助于理解本书中的内容（有些内容跟本书是交叉的）。本书虽会涉及这些领域，但只会对必要的内容做介绍。我们会列出参考资料供想进一步学习的读者参考。

读者需要拥有一到两个学期大学水平的编程经验，包括了解基本数据结构。我们不会涉及编程和具体实现的问题，但算法和数据结构是我们的核心。同数学方面的基础知识一样，在本书中我们会简要介绍基本的信息，同时列出标准教材和知识来源供读者参考。

相关图书

与本书有关的图书包括唐纳德·E.克努特写的《计算机程序设计艺术》（The Art of Computer Programming），塞奇威克和韦恩（Wayne）写的《算法（第4版）》（Algorithms, Fourth Edition），科门（Cormen）、莱瑟森（Leiserson）、里维斯特（Rivest）和斯坦（Stein）写的《算法导论》（Introduction to Algorithms），以及我们自己写的《分析组合论》（Analytic Combinatorics）。本书可以作为这些书的补充材料。

从基本思路上来说，本书与唐纳德·E.克努特的书是最相似的。但本书的重点是算法分析中的数学技术，而唐纳德·E.克努特的那些书是内容更丰富的百科全书，其中算法的各种性质是主角，算法分析方法只是配角。本书可以作为学习唐纳德·E.克努特书中进阶内容的基础。本书还涵盖了唐纳德·E.克努特的书诞生之后在算法分析领域出现的新方法和新成果。

本书尽可能地涵盖各种重要、有趣的基础算法，例如，塞奇威克和韦恩的《算法（第4版）》中所介绍的那些算法。《算法》一书涵盖了经典的排序、搜索和用于处理图和字符串的算法，本书的重点是介绍用于预测算法性能和比较算法性能优劣的数学知识。

科门（Cormen）、莱瑟森（Leiserson）、里维斯特（Rivest）和斯坦（Stein）合著的《算法导论》是算法方面的标准教材，其中提供了关于算法设计的各种资料。《算法导论》一书（及相关的资料）关注的是算法设计和理论，大部分是基于最差性能边界的。而本书关注的则是算法分析，尤其是各种科学研究（而不是理论研究）所需的技术。第1章就是为此做铺垫的。

本书还会介绍分析组合学，它可以让读者开阔视野，也有助于开发用于新研究的高级方法和模型，而且不局限于算法分析，它还可以用于组合学和更广泛的科学应用。那一部分对读者的数学水平要求更高一些，差不多需要本科高年级学生或研究生一年级学生的水平。当然，仔细阅读本书也有助于读者学习相关的数学知识。我们的目标是尽可能让读者感兴趣，有动力进行更深入的学习。

如何使用这本书

本书读者在数学和计算机科学方面的知识储备肯定是不一样的。所以，读者要注意本书的结构：全书共9章，第1章是导论，介绍算法分析，第2～5章介绍数学方法，最后的4章是组合结构及其在算法分析中的应用。具体如下：

导论

第1章　算法分析

数学方法

第2章　递归关系

第3章　母函数

第4章　渐近逼近

第5章　分析组合

组合结构及其在算法分析中的应用

第6章　树

第7章　排列

第8章　字符串与字典树

第9章　单词与映射

第1章介绍全书的主要内容，帮助读者理解本书的基本目标以及其余各章的目的。第2～4章涵盖了离散数学中的方法，重点是基本概念和技术。第5章是一个转折点，其中涵盖了分析组合学的内容。计算机和计算模型的出现带来了很多新问题，这些问题往往涉及大型的离散结构。分析组合学就是研究这些离散结构以解决新出现的问题的。第6～9章则回到了计算机科学，内容涵盖了各种组合结构的属性、它们与基本算法的关系以及分析结果。

我们试图让本书是自包含的，本书的组织结构可以让教师很方便地根据学生和教师自己的背景及经验选取要重点讲解的部分。一种比较偏数学的教学方案是重点讲解本书第2～5章的理论和证明，然后过渡到第6～9章的相关应用。另一种比较偏计算机科学的方案是简要介绍第2～5章的数学工具，将重点放在第6～9章与算法有关的内容上。但我们的根本目标还是要让绝大部分的学生能通过本书学习到数学和计算机科学的新知识。

本书还罗列了很多参考资料以及数百个习题，鼓励读者去研究原始材料，以便更深入地研究本书中的内容。根据我们的教学经验，教师可以通过计算实验室和家庭作业，灵活地组织授课和阅读材料。本书的内容为学生深入学习诸如Mathematica、Maple或Sage之类的符号计算系统提供了一个很好的框架。更重要的是，对学生而言，通过比较数学研究结果和实际测试结果得出的结论是有重要价值的，不可忽略。

配套网站

本书的一个重要特点就是拥有配套的网站aofa.cs.princeton.edu。这个网站是免费的，提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，其中有一些关于算法和分析组合学的网站。这些材料对讲授这些内容的教师和自学者都很有帮助。

致谢

我们非常感谢普林斯顿大学、INRIA和NSF（美国国家科学基金会），它们是我们这本书的主要资助者。其他的资助来自布朗大学、欧洲共同体（Alcom项目）、美国国防分析研究院、法国研究与技术部、斯坦福大学、布鲁塞尔自由大学和施乐帕克研究中心。本书历时多年才得以付梓，在此不可能一一列出为本书提供支持和帮助的人和机构，我们对此深表歉意。

正如书中所说，唐纳德·E.克努特对本书有重要的影响。

过去几年，在普林斯顿、巴黎和普罗维登斯听过我们讲课的学生们为本书提供了宝贵的反馈意见。全世界各地的学生和教师也为本书的第1版提出了很多好建议。在此特别感谢菲利普·杜马斯（Philippe Dumas）、摩德凯·戈林（Mordecai Golin）、赫尔穆特·普罗丁格（Helmut Prodinger）、米歇尔·索里亚（Michele Soria）、马克·丹尼尔·沃德（Mark Daniel Ward）和马克·威尔逊（Mark Wilson）的帮助。

弗利佩·弗拉若莱和罗伯特·塞奇威克　1995年9月于科孚岛

罗伯特·塞奇威克　2012年12月于巴黎