本书通过算法所解决的现实世界的实例来介绍各种算法的思想和技术细节。算法用伪代码给出，使得后续可以很容易地用一种计算机语言来实现。
无
正如同时代大多数人一样，我也是听着这样的话长大的：“游手好闲，魔鬼也嫌。”我是个乖孩子，人们说什么，我就信什么，而且一直抱着要勤奋工作的道德信条。如今，尽管我的道德信条仍控制着我的行为，但是我的看法已然经历了一场革命。我认为在这个世界上人们做的工作实在是太多了，虽说工作即美德，但现代工业国家更提倡一些与过去全然不同的新理念。
——伯特兰·罗素，《闲暇颂》（1932）
本书是关于算法（algorithm）的，算法就是我们为了不去做某些事情而做的事，是我们为了避免工作而做的工作。凭借我们的发明，我们一直在用大脑解放身体。而借助算法，我们可以用大脑解放大脑。
减少人类的劳动是一项高尚的任务。我们应该使用机器尽可能地减少辛苦劳作，这一思想已深深植根于我们的头脑中，令我们能减少数世纪以来已习以为常的枯燥、繁重工作。这是一件美妙的事，而且，就像“避免”体力劳动一样，我们没有理由不追求“避免”脑力劳动。辛苦的、沉闷的、重复性的劳动对人类创造性是毒药，我们理应尽力避免，而算法恰恰能帮助我们做到这一点。
此外，数字技术如今能成就很多壮举，它并不令人烦乱厌恶，而是符合人性本质。机器识别和合成语音、翻译文章、分类并总结文档、预报天气，都是在大量素材中以不可思议的准确性查找相应的模式、运行其他机器、做数学、在博弈中战胜我们，以及帮助我们发明其他机器。所有这些都是用算法做到的，机器完成这些工作就能让我们少做一些，给予我们时间追求自己的兴趣，甚至给予我们时间和机会发明进一步减少日常工作的更好算法。
算法并非始于计算机时代，从古代开始算法就伴随着我们，当然它也并不局限于计算机科学。我们现在已经很难找到一门完全未被算法改变的学科了。因此，很多人在不知不觉中就接触了算法，他们发现：对于他们的学科而言，算法已经成为一个重要组成部分，尽管这门学科看起来与计算机的距离那么遥远。这样，他们有必要学习算法，以便能理解、使用算法。
即使是一些简单的事情和日常工作，也令人惊讶地在日复一日地浪费着我们的劳动，就是因为我们没有使用一些正确的思想。作者常常看到，人们在日常办公过程中做的一系列操作，其实可以一眨眼就做完，只要他们知道如何避免繁冗的劳作——当然，并不是通过逃避来避免（一些人擅长于此），而是让计算机帮他们做这些事（应该有更多人精于此）。
目标读者
本书的撰写目标是作为算法的第一本入门书籍。如果你是计算机科学专业，可以将本书作为入门书籍，然后继续钻研进阶教材。算法是计算的核心，像本书这样的介绍只是走马观花。
还有很多读者从事其他职业，但意识到算法已成为其职业的必备工具。在很多学科中，几乎不可能不使用算法。本书希望为这样的读者而服务：他们需要使用和理解算法，作为其工作和学习的一部分（哪怕不是核心部分）。有很多读者都是这种情况。
然后就是那些可能要使用算法（无论多么小或多么简单的算法）来简化工作、避免在琐事上浪费时间的读者。需要花费一个勤奋的劳动者数小时时间的任务，很可能用现代脚本语言写的寥寥几行计算机代码瞬间即可完成。有时，一个毫无经验的人突然间顿悟，就能做出如此成绩，因为算法思维并非一些耀眼的专业人士的特权。
要在现代社会中正常生活，基础的数学和科学知识是必需的，这一点恐怕没有人能充分反驳。类似地，不掌握基本的算法知识，也不太可能成为当代社会中有作为的一分子。算法已成为人们日常生活的基础。
读者须知
只有计算机科学家才能理解算法，这种看法是错误的。算法由执行任务的指令组成，所有人都能理解它。但为了更有效地使用算法以及能从像本书这样的书籍中受益，读者应该掌握一些基本技能。
读者不必是一名有经验的数学家，但应能比较顺利地接受一些基本的数学概念和符号描述。本书涉及的数学知识不会超过普通中学所讲授的内容。读者不必了解高等数学，但必须知道怎样证明，因为我们证明算法正确工作的方式与数学证明一样遵循逻辑步骤。这并不意味着在本书中我们会使用大量完整的数学证明，但读者应该理解我们是如何使用证明的。
读者不必是一名熟练的程序员，但应该对计算机的工作原理、如何编写程序以及计算机语言是如何构造的有一个基本理解。我们不要求读者深入理解任何一方面，实际上，最好是在学习算法的过程中阅读本书。计算机系统和算法是密不可分的，两者相互解释。
保持好奇心是必要的。算法是用来高效求解我们遇到的问题的。每当你思考“这是更好的解决方法吗？”，你其实就是在寻找算法。
风格
本书的主旨是令算法尽量简单，避免读者有挫败感。如果你在阅读一本书的时候发现它已超出了你的理解力，那么很可能它不适合你；如果你不理解一本书的内容而对其感到畏惧，那就表明你有了挫败感。我们努力避免本书陷入这样的境地，这需要对介绍的内容进行一定的简化，还意味着我们在呈现某些内容时不能给出其完整的证明。
简化一些内容以及忽略一些复杂的内容并不意味着读者学习本书时就不必积极努力了：这正是我们努力不使读者有挫败感的地方。我们假定读者真的想学习算法，这的确需要努力和时间，你投入的时间和精力越多，你的收获也越大。
我们稍微讨论一下文学性，有一些书会强烈地吸引你，带你徜徉其中，你读着这些书，被其深深吸引，一口气读完，完全没有意识到时间的流逝。我们说的当然不是那些粗制滥造的读物。阿贝尔·加缪的《鼠疫》并不是一本难读的书，但没有人会质疑它是一部严肃的、有深度的文学作品。
其他一些书则需要完整的脑力操练。这些书较难读懂，但令读它们的人获得了巨大的成就感，甚至令努力读完它们的人获得排他的优越感：并不是每个人都喜欢詹姆斯·乔伊斯的《尤利西斯》、托马斯·品钦的书以及大卫·福斯特·华莱士的书，但几乎没有人对于努力读完这些书而感到后悔。
还有其他一些书介于这两类书之间。可能《万有引力之虹》对你来说有些过于偏向“作者书籍”了，但你能这么评价《卡拉马佐夫兄弟》和《安娜·卡列尼娜》吗？
本书努力做到介于两类书之间。它当然不是作为智力成果来呈现，但你还是要付出相当的努力来阅读本书。作者将带领你踏上算法学习之路，但不会抱着你前进，在这条路上向前走只能靠你自己，这也是本书尽量不让你有挫败感的做法。我们假定你是个聪明人，愿意学习新事物，并且明白在学习上必须积极努力。天下没有免费的午餐，付出才有回报。
伪代码
在过去几年中，一个年轻人如果精通一门编程语言，就有望获得一份计算机相关的工作。但现在情况已经变了。被广泛使用的好的编程语言非常多，因为如今计算机所做的事情比20年前多得多，而不同的语言适合于不同的用途。关于语言的争论是愚蠢的、适得其反的。如今计算机在帮我们做着很多美好的事情，带来的一个可喜结果就是人们积极地探索使用计算机的新方式，这方面的努力不断催生出新的编程语言并促进老的编程语言进化。
作者确实更偏好某些计算机语言，但将个人偏好强加于读者是不公平的。而且，计算机语言的流行趋势潮涨潮落，昨日最爱可能就是明日黄花。为了让本书受众广泛，生命力长久，作者未在书中纳入使用实际编程语言的例子，算法都是使用伪代码来描述的。伪代码比实际的计算机代码更好理解，而且可以避免真实计算机语言必然会有的弱点。基于伪代码进行一些推断通常也更容易，当你试图更深入地理解一个算法时，必须将它的一部分写出来，此时使用伪代码比真实代码更简单，因为使用真实代码必须仔细注意语法。
也就是说，如果你不真正编写计算机代码来实现一个算法，那么是很难用好它的。我们在本书中采用伪代码，并不意味着读者应该对计算机代码采取一种漫不经心的态度。只要条件允许，对本书介绍的每个算法读者都应该选择一种编程语言去实现它。当你设法编写计算机程序正确实现了一个算法时，所获得的成就感是你预料不到的。
如何阅读本书
阅读本书的最好方式是按顺序阅读，因为后面章节会用到前面章节给出的一些概念。开始，你会遇到所有算法都会用到的基本数据结构，后面章节中也的确会用到这些数据结构。但是，一旦基础打好，你就可以选择感兴趣的章节去阅读了。
因此，你应该从第1章开始，在这一章中你将看到后续章节是如何组织的：每一章都以问题描述开始，然后介绍能解决此问题的算法。第1章还介绍了本书采用的伪代码规范、基本术语以及你将遇到的第一个数据结构：数组和栈。
在第2章中，你将第一次看到图及其遍历方法。第2章还将介绍递归，因此，即使你之前接触过图，但如果并不完全确定是否掌握递归的话，你还是不能跳过这一章。第2章还将介绍在其他章节的算法中会反复遇到的一些数据结构。然后，在第3章中，我们将转向压缩问题并介绍两种不同的压缩方法，自然而然地，会介绍一些更重要的数据结构。
第4章和第5章讨论加密算法。这部分内容完全不同于图算法和压缩算法，但它是一个重要的算法应用领域，特别是近年来个人数据存在于各种地方和各类设备中，而各色人等都想窥探这些数据。这两章与其他章节多少有些独立，只有一些重要部分是在其他章节中给出的，例如，如何选取大素数留待第16章介绍。
第6章到第10章介绍了一些图相关的问题：任务排序、迷宫寻路、如何确定链接到其他对象的对象的重要性（例如互联网中的网页）以及图如何用于选举。迷宫寻路的应用远超你的想象，从段落排版到互联网路由和金融套利，它的一个变体还应用于投票问题中，因此第7章、第8章和第10章可以看作一个整体。
第11章和第12章讨论两个基础的计算问题：搜索和排序。这两个主题的内容可以填满一卷书，而且确实有这样的书。我们将介绍一些常用的搜索和排序算法。当讨论搜索问题时，我们会借机介绍一些额外内容，例如在线搜索（数据项是流式到来的，我们在其中搜索指定内容，因此无法事后修正决策）和无标度分布，研究者在其关心的领域内常会遇到这些问题。第13章介绍另外一种保存和提取数据的方法——哈希，这是一种非常有用、常用且很精致的方法。
第14章介绍一种分类算法：算法基于一组实例学习如何分类数据，然后我们就可以用它来分类新的未曾见过的实例。这是机器学习的一个例子，随着计算机越来越强大，机器学习的重要性得到了极大的提升。这一章还会介绍信息论的基本思想，这是另一个与算法相关的迷人领域。第14章与本书其他章节的不同之处在于，它还呈现了一个算法如何通过调用更小的算法来完成其部分任务，这与计算机程序由完成特定任务的小的部件构成是相似的。这一章还展示了本书其他部分介绍的数据结构是如何在分类算法的实现中起重要作用的。如果读者想要了解一个高层算法的细节是如何实现的——这是算法转换为程序的关键步骤，那么这一章会很吸引你。
第15章探究符号序列（字符串）以及如何在字符串中查找内容。每当我们在一段文本中查找某些东西，就是在用计算机执行这个操作，如何高效地执行这个操作人们还不甚清楚。但幸运的是，有一些快速、优雅地完成这个操作的方法。此外，符号序列还能表示很多其他类型的事物，因此字符串匹配能应用到很多领域中，例如生物学。
最后，第16章介绍随机算法。随机算法的应用范围之广令人惊讶，因此这一章只能包含其中一小部分。除此之外，随机算法还解答了本书前面章节中遇到的一些问题，例如，如何找到密码学中要用到的大素数，还有与投票相关的，即如何统计你的投票的影响。
课程使用
本书中的素材可用于一个学期的算法课程，课程重点是理解算法的主要思想，但不会深入每个主题的技术处理。来自不同学科的学生，如商学和经济学，生命科学、社会学和应用科学，或者数学和统计学等，都可将本书作为一门入门课程的主教材，再辅以编程作业，要求学生实现真实有用的算法实例。对于计算机科学的学生，可以将本书作为一本非正式的介绍性书籍，它能激励学生通过阅读更深入的技术书籍彻底领略算法的深度和优美。
致谢
当我第一次向MIT出版社提出撰写本书的想法时，如何实现这一想法还完全没有头绪，但出版社的人员如此出色，没有他们的支持，这个想法也不会存在。Marie Lufkin Lee在本书撰写的整个过程中一直温柔地鼓励我，哪怕是在我延期时。Virginia Crossman、Jim Mitchell、Kate Hensley、Nancy Wolfe Kotary、Susan Clark、Janice Miller、Marc Lowenthal以及Justin Kehoe都在不同阶段给予我帮助，并承担了匿名审稿的任务。当我沉迷于LaTeX时，Amy Hendrickson给予了我帮助。
Marios Fragkoulis对部分书稿提出了详细的反馈，Diomidis Spinellis抽出时间就如何改进书稿给了我很棒的建议。Stephanos Androutsellis-Theotokis、George Theodorou、Stephanos Chaliasos、Christina Chaniotaki以及George Pantelis都很友善地指出了书稿中的很多错误，遗留的其他任何尴尬的错误和疏忽都完全是我个人的责任。
当然，我还要向Eleni、Adrian和Hector致以敬意，本书得以出版真的首先要归功于他们。
最后的话
如果你把algorithm（算法）误写为algorhythm，你就得到了一个意为“痛苦的节奏”的混合词，因为在希腊语中algos的意思是痛苦。在现实中，“算法”一词源自波斯数学家、天文学家和地理学家阿尔·花剌子模（约公元780～公元850）的名字。希望本书能吸引你而不是让你感到痛苦，让我们来学好、用好算法吧！
计算机\算法
算法的第一本入门书籍，
带领你踏上算法学习之路。
算法可以代替我们做许多重复的事情，它由执行任务的指令组成，这些任务通常是枯燥且重复的。从简单的构造块开始，计算机算法使机器能够识别和产生语音、翻译文本、分类和总结文档、描述图像和预测天气。你只要在现代脚本程序中使用几行代码，就可以瞬间完成原本需要耗时数小时才能完成的任务。本书通过真实世界中需要解决的实际问题来介绍算法，这些算法用伪代码表示，可以很容易地用计算机语言实现。
本书介绍的算法简单易懂，避免读者有挫败感。读者仅需具备基本的数学知识并大致了解计算机的工作原理，书中会解释所有其他必要的概念。本书在介绍了伪代码规范、基本术语和数据结构的背景知识之后，讨论了压缩、加密、图、搜索和排序、哈希、分类、字符串和随机等算法。每章都描述了实际问题，然后给出了解决这些问题的算法。示例说明了算法的广泛应用，包括解决段落换行的最短路径、投票系统中的最强路径、歌曲识别的哈希、投票权力的蒙特卡罗方法和机器学习的熵。
作者简介
帕诺斯·卢里达斯
（Panos Louridas）
曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授。在加入高校之前，曾在投资银行担任高级软件工程师。
本书广泛地探讨算法思想，避免通常的“追热度”做法，它包括了大多数算法入门书籍都不会涉及的投票系统和文本压缩等高级主题，让初学者在会走路之前就跑起来了！
—— Steven Skiena
石溪大学计算机科学系教授
算法是计算机的核心思想。帕诺斯·卢里达斯写了一本漂亮的书，指导你浏览所有主要算法。这本书非常清晰易读，不把你当作专家。会以具体且相关的范例而不是抽象方式来介绍算法。这本书可以作为学生的入门教材，也可以被任何有计算机基础的人阅读。
—— Noson S. Yanofsky
布鲁克林学院计算机与信息科学系教授
算法统治着当今世界。卢里达斯找到了一种方法，将算法的宏大思想和复杂细节与根植于真实世界的应用结合起来。如果你想要知道各种领域如何运用算法，这本书是一个重要的指南。
—— Mung Chiang
普林斯顿大学Arthur LeGrand Doty教授
前言
第1章股票跨度1
1.1算法2
1.2运行时间和复杂度5
1.3使用栈求解股票跨度9
注释13
习题14
第2章探索迷宫15
2.1图16
2.2图表示20
2.3深度优先图遍历25
2.4宽度优先搜索32
注释35
习题36
第3章压缩算法38
3.1压缩40
3.2树和优先队列42
3.3赫夫曼编码44
3.4伦佩尔-齐夫-韦尔奇压缩算法50
注释58
习题58
第4章秘密60
4.1一个解密挑战61
4.2一次性密码本64
4.3AES加密67
4.4迪菲-赫尔曼密钥交换72
4.5快速模幂运算76
注释79
习题80
第5章秘密分割81
5.1公钥密码学81
5.2RSA密码系统83
5.3消息哈希90
5.4互联网通信匿名化91
注释95
习题96
第6章排序问题97
6.1拓扑排序98
6.2加权图102
6.3关键路径103
注释108
习题109
第7章行、段落和路径110
7.1最短路径112
7.2迪杰斯特拉算法114
注释118
习题119
第8章路由和套利120
8.1互联网路由122
8.2Bellman-Ford(-Moore)算法125
8.3负权重和环130
8.4套利133
注释135
第9章什么最重要136
9.1PageRank思想136
9.2超链接矩阵137
9.3幂方法139
9.4Google矩阵142
注释145
第10章投票力147
10.1投票系统148
10.2Schulze方法150
10.3Floyd-Warshall算法158
注释159
第11章蛮力、秘书和二分法160
11.1顺序搜索160
11.2匹配、比较、记录和关键字162
11.3马太效应和幂律163
11.4自组织搜索167
11.5秘书问题170
11.6二分搜索172
11.7在计算机中表示整数175
11.8再探二分搜索179
11.9比较树180
注释183
第12章各种各样的排序算法185
12.1选择排序185
12.2插入排序188
12.3堆排序191
12.4归并排序197
12.5快速排序205
12.6多不胜选210
注释212
习题212
第13章寄存室、鸽巢和桶213
13.1将关键字映射到值213
13.2哈希216
13.3哈希函数218
13.4浮点数表示和哈希223
13.5碰撞225
13.6数字指纹231
13.7Bloom过滤器235
注释242
习题243
第14章比特和树244
14.1将占卜看作通信问题244
14.2信息和熵246
14.3分类249
14.4决策树250
14.5属性选择253
14.6ID3算法256
14.7内在机制261
14.8奥卡姆剃刀法则266
14.9代价、问题和改进266
注释268
习题269
第15章字符串算法271
15.1蛮力字符串匹配273
15.2Knuth-Morris-Pratt算法275
15.3Boyer-Moore-Horspool算法283
注释288
习题288
第16章听从命运的安排290
16.1随机数291
16.2随机抽样296
16.3权力游戏300
16.4搜索素数307
注释313
习题314
参考文献315
索引326
