这本书会是你在算法分析道路上最好的养料

算法对于我们的世界是多么重要。自计算机科学诞生之日起，关于算法的研究就一直是一个核心话题。

现代计算机科学中充满了各种各样的算法，许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如：

• 提出单源最短路径算法的迪可斯特朗（Edsger Dijkstra，1972年图灵奖得主）
• 提出字符串匹配算法的高德纳（Donald Knuth，1974年图灵奖得主）
• 提出多源最短路径算法的弗洛伊德（Robert Floyd，1978年图灵奖得主
• 提出快速排序算法的霍尔（Antony Hoare，1980年图灵奖得主） ……

这其中不得不提一个人——高德纳，他是最年轻的图灵奖得主纪录保持者（获奖时年仅36岁），以计算机算法设计与分析领域经典巨著The Art of Computer Programming（《计算机程序设计艺术》）而广为人知。

高德纳 （Donald Knuth）

The Art of Computer Programming

作为导师，高德纳一生共指导过28位博士生，而其中一位就是名满江湖的算法宝红书Algorithms (4th edition)作者罗伯特·塞奇威克（Robert Sedgewick）。

罗伯特·塞奇威克（Robert Sedgewick）

塞奇威克曾经是普林斯顿大学计算机科学系的创立者暨首任系主任，他同时还是著名的Adobe公司的董事。作为一位世界知名的计算机科学家，塞奇威克于1997年当选ACM（Association for Computing Machinery，国际计算机学会）院士，并因从“对称二叉树”中导出了红黑树而享誉计算机界。

（图片来自维基百科）

塞奇威克与挚友费利佩·弗拉若莱（Philippe Flajolet，被称为“分析组合学之父”）曾合作撰写过数本算法分析领域的著作，其中就包括这部在全世界范围内广泛流传的经典之作An Introduction to the Analysis of Algorithms（《算法分析导论》）。

An Introduction to the Analysis of Algorithms

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

作为行业代表著作，高德纳大师在此书的序言中称赞道：

“Sedgewick和Flajolet不仅是算法分析领域的专家，同时也是算法分析的布道大师。我坚信，这本书会让每一位细细品读的计算机研究人员从中获益。”

可惜，天妒英才，2011年3月，休假期间的塞奇威克惊悉多年的老友弗拉若莱突然离世。悲痛万分的塞奇威克怀着对逝者的无限缅怀写了感人至深的悼词：“弗拉若莱的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者，他们可再续他的数学梦想。”在这样的背景下，塞奇威克以极大的热情投入工作，历经数百个日夜，终于在2012年10月将本书的第2版付梓。

An Introduction to the Analysis of Algorithms,2E

第 2 版不仅对书中图片和代码进行了更新，还补充了新章节。塞奇威克坚信弗拉若莱的精神会在后来人的工作中得到永生，进而希冀本书读者能够循着弗拉若莱的脚步，继续追求他的数学梦想。

如今本书中文版《算法分析导论（第2版）》已出版上市，全书共 9 章，第 1 章是导论；第 2～5 章介绍数学方法；第 6～9 章介绍组合结构及其在算法分析中的应用。除每章包含的大量习题以及参考文献外，本书还特设配套免费学习网站，为读者提供了很多关于算法分析的补充材料，包括课件和相关网站的链接，帮助读者提高学习兴趣，完成更深入的学习，感兴趣的读者。

• 算法分析是推动现代计算基础技术发展的重要力量，本书囊括众多算法分析的应用实例。
• 无数人对从数学角度分析算法产生兴趣，但很难学到相关方法和模型，本书完整介绍该领域主要技术和成果。
• 作者既精通经典数学又熟谙计算机科学，看重用于算法性能预测的数学基础及从性能角度比较算法。
• 天才般贯通与揭露数学世界的离散数学|分析组合学|实分析与计算机科学领域的算法|数据结构之奥义。

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

— — 译者序