译者序
2014年的冬天，一部讲述“计算机科学之父”艾伦·图灵（Alan Turing）传奇人生的传记电影在美国上映，这部影片就是《模仿游戏》。次年，该片荣获第87届奥斯卡金像奖最佳改编剧本奖，以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的7项提名，一时风光无限。
图灵一生最重要的三大贡献包括图灵机、图灵测试以及破译Enigma密码，其中的每一项都值得全世界感谢和纪念他。在提出图灵测试的论文中，图灵石破天惊地预言了创造出具有真正智能的机器的可能性，这也是人工智能研究的源头。事实上，《模仿游戏》这个名字正是图灵那篇著名论文第1章的标题。后人为了纪念图灵对计算机科学所做出的巨大贡献，将该领域的最高奖命名为“图灵奖”。而破译Enigma密码更是直接帮助盟军在战场上取得了先机，拯救了无数人的性命并最终取得第二次世界大战反法西斯阵营的全面胜利。
尽管前面提到的两大贡献已是功若丘山，但笔者这里将从图灵的另外一个贡献——图灵机谈起，因为这与本书所要讨论的话题息息相关。为此，我们还得把时间再往前推。1900年，德国数学家大卫·希尔伯特（David Hilbert）在国际数学家大会上做了题为《数学问题》的演讲，提出了著名的希尔伯特之23个问题。尽管此后的数学发展远远超过了希尔伯特的预料，但他所提出的这23个问题仍然对20世纪的数学发展起到了重要的推动作用。
希尔伯特的第10个问题是要设计一个算法来测试多项式是否有整数根。他没有使用“算法”这个术语，而是采用了下面这种表述：“通过有限多次运算就可以决定的过程。”有意思的是，从希尔伯特对这个问题的陈述中可以看出，他明确地要求设计一个算法。因此，显然他假设这样的算法是存在的，人们所要做的只是找到它。现在我们知道，这个任务是无法完成的，即它是算法上不可解的。但对那个时期的数学家来说，以他们对算法的直观认识，得出这样的结论是不可能的。
非形式地说，算法是为实现某个任务而构造的简单指令集。用日常用语来说，算法又被称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学资料中就包含执行各种各样计算任务的算法描述。例如，我国古代数学经典《九章算术》中就记述了包括求最大公约数、求最小公倍数、开平方根、开立方根等在内的诸多算法。
虽然算法在数学中已有很长的历史，但在20世纪之前，算法本身一直没有精确的定义。数学家面对希尔伯特的第10个问题束手无策。由于缺乏对算法本身的精确定义，要证明某个特定任务不存在算法就更不可能了。要想破解希尔伯特的第10个问题，人们不得不等待算法的精确定义出现。
直到1936年，曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中的应用》的论文。该文最终于1937年正式发表，并立即引起了广泛关注。在论文中，图灵描述了一种可以辅助数学研究的机器，也就是后来被称为“图灵机”的抽象系统。与此同时，另外一位数学家阿隆佐·丘奇（Alonzo Church）也独立地提出了另外一套系统，即所谓的Lambda演算。图灵采用他的图灵机来定义算法，而丘奇则采用Lambda演算来定义算法，后来图灵证明这两个定义是等价的。由此，人们在算法的非形式概念和精确定义之间建立了联系，即算法的直觉概念等价于图灵机，这就是所谓的“丘奇－图灵”论题。
“丘奇－图灵”论题提出的算法定义是解决希尔伯特第10个问题所需的，而第10个问题的真正解决则直到1970年，借助于丘奇与图灵的杰出贡献，卡里·马提亚塞维齐（Yuri Matiyasevich）在马丁·戴维斯（Martin Davis）、希拉里·普特纳姆（Hilary Putnam）和朱莉娅·罗宾逊（Julia Robinson）等人工作的基础上，最终证明检查多项式是否有整数根的算法是不存在的。上述四人的名字也紧紧地同希尔伯特的第10个问题联系在了一起。破解希尔伯特的第10个问题的过程更像一场声势浩大又旷日持久的国际协作和学术接力。每个人的工作都必不可少，而且大家都感觉已经相当接近问题的最终答案。历史见证了马提亚塞维齐敏锐地接过最后一棒并完成终点冲刺的伟大一幕。更有意思的是，彼时正值美苏冷战最为紧张的时期，两个超级大国之间的正常学术交流几乎完全中断。但这或许就是科学无国界的一个重要体现，尽管国家层面上双方剑拔弩张，而科学家在私下仍然以一种惺惺相惜的默契方式彼此神交。特别是在得知苏联数学家完成了最终的证明时，美国同行都相当振奋和由衷地喜悦，这不得不说是学术界的一段佳话。
回顾建立算法形式化定义和破解希尔伯特第10个问题的那段风起云涌的历史，我们不得不由衷地感叹：算法对于我们的世界是多么重要。可以这样说，自计算机科学诞生之日起，关于算法的研究就一直是一个核心话题。现代计算机科学中充满了各种各样的算法，许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如，提出单源最短路径算法的艾兹格·迪科斯彻（Edsger Dijkstra）[1]、提出字符串匹配算法的唐纳德·E.克努特，中文名为高德纳（Donald E.Knuth）[2]、提出多源最短路径算法的罗伯特·弗洛伊德（Robert Floyd）[3]，以及提出快速排序算法的安东尼·霍尔（Antony Hoare）[4]等。其中，高德纳是最年轻的图灵奖得主这一纪录的保持者（获奖时年仅36岁），并以计算机算法设计与分析领域的经典巨著《计算机程序设计艺术》而广为人知。
[1] 1972年图灵奖得主。
[2] 1974年图灵奖得主。
[3] 1978年图灵奖得主。
[4] 1980年图灵奖得主。
作为导师，高德纳一生共指导过28位博士生，而本书作者之一的罗伯特·塞奇威克（Robert Sedgewick）便是其中之一。塞奇威克是普林斯顿大学计算机科学系的创立者暨首任系主任，还是著名的Adobe公司的董事。作为一位世界知名的计算机科学家，塞奇威克于1997年当选ACM（Association for Computing Machinery，国际计算机学会）会士，并因从对称二叉树中导出了红黑树而享誉计算机界。
塞奇威克与费利佩·弗拉若莱（Philippe Flajolet）曾合作撰写过数本算法分析领域的著作，本书即为其中一部在全世界范围内广泛流传的经典之作。弗拉若莱是法国计算机科学家、法国科学院院士，被称为“分析组合学之父”。他与合作者共同提出的Flajolet-Martin算法更是当今互联网与大数据时代背景下，网站分析统计的重要基石。
然而，天妒英才，2011年3月，弗拉若莱突然离世。悲痛万分的塞奇威克怀着对逝者的无限缅怀写了感人至深的悼词：“弗拉若莱的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者，我们会继续追寻他的数学梦想。”在这样的背景下，塞奇威克以极大的热情投入工作，历经数百个日夜，终于在2012年10月将本书的第2版付梓。塞奇威克坚信弗拉若莱的精神会在后人的工作中得到永生，进而希冀本书的读者能够循着弗拉若莱的脚步，继续追求他的数学梦想。
本书全面系统地介绍了算法分析中需要使用的基本技术，所涉及的内容既有来自包括离散数学、初等实分析、组合数学等在内的经典数学课题，也有来自算法及数据结构等的计算机科学课题，像递归、母函数、树、字符串、映射以及散列等算法分析话题均有讨论。可以说本书是一本研究算法分析的权威之作。
作为译者，我们希望自图灵以来的算法研究能够在更宽阔的范围内发扬光大，尤其希望中国的计算机科研人员能够从本书中找到启迪研究工作的智慧。同时，希望通过本书向神交已久的两位大师——塞奇威克和弗拉若莱送上最崇高的敬意。
最后，本书翻译工作的完成有赖于数位合作者的倾心付出，其中常青翻译了本书的第1至6章，左飞翻译了第8、9章，于佳平翻译了第7章。其他参与本书翻译和校对工作的人员还有李振坡、邵臣、叶剑、赵冰冰、贾啸天、钱文秀、丁星芸、李晓华、黄帅。自知论道须思量，几度无眠一文章。因时间和水平有限，纰漏与不足之处在所难免，译者恳切地期望广大同行及读者朋友不吝批评斧正。