真实世界的算法：初学者指南

学习算法的启蒙读本

算法尽量简单，避免读者有挫败感，仅需基本数学基础和计算机常识知识

通过真实世界需要解决的实际问题来介绍算法思想

为各领域高效运用算法提供重要指南

算法的第一本入门书籍，带领你踏上算法学习之路。
算法可以代替我们做许多重复的事情，它由执行任务的指令组成，这些任务通常是枯燥且重复的。从简单的构造块开始，计算机算法使机器能够识别和产生语音、翻译文本、分类和总结文档、描述图像和预测天气。你只要在现代脚本程序中使用几行代码，就可以瞬间完成原本需要耗时数小时才能完成的任务。本书通过真实世界中需要解决的实际问题来介绍算法，这些算法用伪代码表示，可以很容易地用计算机语言实现。
本书介绍的算法简单易懂，避免读者有挫败感。读者仅需具备基本的数学知识并大致了解计算机的工作原理，书中会解释所有其他必要的概念。本书在介绍了伪代码规范、基本术语和数据结构的背景知识之后，讨论了压缩、加密、图、搜索和排序、哈希、分类、字符串和随机等算法。每章都描述了实际问题，然后给出了解决这些问题的算法。示例说明了算法的广泛应用，包括解决段落换行的*短路径、投票系统中的*强路径、歌曲识别的哈希、投票权力的蒙特卡罗方法和机器学习的熵。

作者简介：

帕诺斯·卢里达斯
（Panos Louridas）
曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授。在加入高校之前，曾在投资银行担任高级软件工程师。

译者简介：

王刚 南开大学计算机学院教授、博士生导师。研究兴趣包括海量信息存储、并行与分布式计算、搜索引擎等。曾翻译多部计算机领域名著，包括《C++程序设计语言）（原书第4版）》《C++程序设计原理与实践（原书第2版）》《C++ Primer（中文版 第5版）》《C++ Primer Plus（第6版 中文版）》《算法导论（原书第3版）》（合译）等。

本书广泛地探讨算法思想，避免通常的“追热度”做法，它包括了大多数算法入门书籍都不会涉及的投票系统和文本压缩等高级主题，让初学者在会走路之前就跑起来了！
—— Steven Skiena石溪大学计算机科学系教授

算法是计算机的核心思想。帕诺斯·卢里达斯写了一本漂亮的书，指导你浏览所有主要算法。这本书非常清晰易读，不把你当作专家。会以具体且相关的范例而不是抽象方式来介绍算法。这本书可以作为学生的入门教材，也可以被任何有计算机基础的人阅读。
—— Noson S. Yanofsky布鲁克林学院计算机与信息科学系教授

算法统治着当今世界。卢里达斯找到了一种方法，将算法的宏大思想和复杂细节与根植于真实世界的应用结合起来。如果你想要知道各种领域如何运用算法，这本书是一个重要的指南。
—— Mung Chiang普林斯顿大学Arthur LeGrand Doty教授

前言
第1章股票跨度1
11算法2
12运行时间和复杂度5
13使用栈求解股票跨度9
注释13
习题14
第2章探索迷宫15
21图16
22图表示20
23深度优先图遍历25
24宽度优先搜索32
注释35
习题36
第3章压缩算法38
31压缩40
32树和优先队列42
33赫夫曼编码44
34伦佩尔-齐夫-韦尔奇压缩算法50
注释58
习题58
第4章秘密60
41一个解密挑战61
42一次性密码本64
43AES加密67
44迪菲-赫尔曼密钥交换72
45快速模幂运算76
注释79
习题80
第5章秘密分割81
51公钥密码学81
52RSA密码系统83
53消息哈希90
54互联网通信匿名化91
注释95
习题96
第6章排序问题97
61拓扑排序98
62加权图102
63关键路径103
注释108
习题109
第7章行、段落和路径110
71最短路径112
72迪杰斯特拉算法114
注释118
习题119
第8章路由和套利120
81互联网路由122
82Bellman-Ford(-Moore)算法125
83负权重和环130
84套利133
注释135
第9章什么最重要136
91PageRank思想136
92超链接矩阵137
93幂方法139
94Google矩阵142
注释145
第10章投票力147
101投票系统148
102Schulze方法150
103Floyd-Warshall算法158
注释159
第11章蛮力、秘书和二分法160
111顺序搜索160
112匹配、比较、记录和关键字162
113马太效应和幂律163
114自组织搜索167
115秘书问题170
116二分搜索172
117在计算机中表示整数175
118再探二分搜索179
119比较树180
注释183
第12章各种各样的排序算法185
121选择排序185
122插入排序188
123堆排序191
124归并排序197
125快速排序205
126多不胜选210
注释212
习题212
第13章寄存室、鸽巢和桶213
131将关键字映射到值213
132哈希216
133哈希函数218
134浮点数表示和哈希223
135碰撞225
136数字指纹231
137Bloom过滤器235
注释242
习题243
第14章比特和树244
141将占卜看作通信问题244
142信息和熵246
143分类249
144决策树250
145属性选择253
146ID3算法256
147内在机制261
148奥卡姆剃刀法则266
149代价、问题和改进266
注释268
习题269
第15章字符串算法271
151蛮力字符串匹配273
152Knuth-Morris-Pratt算法275
153Boyer-Moore-Horspool算法283
注释288
习题288
第16章听从命运的安排290
161随机数291
162随机抽样296
163权力游戏300
164搜索素数307
注释313
习题314
参考文献315
索引326

正如同时代大多数人一样，我也是听着这样的话长大的：“游手好闲，魔鬼也嫌。”我是个乖孩子，人们说什么，我就信什么，而且一直抱着要勤奋工作的道德信条。如今，尽管我的道德信条仍控制着我的行为，但是我的看法已然经历了一场革命。我认为在这个世界上人们做的工作实在是太多了，虽说工作即美德，但现代工业国家更提倡一些与过去全然不同的新理念。
——伯特兰·罗素，《闲暇颂》（1932）

本书是关于算法（algorithm）的，算法就是我们为了不去做某些事情而做的事，是我们为了避免工作而做的工作。凭借我们的发明，我们一直在用大脑解放身体。而借助算法，我们可以用大脑解放大脑。
减少人类的劳动是一项高尚的任务。我们应该使用机器尽可能地减少辛苦劳作，这一思想已深深植根于我们的头脑中，令我们能减少数世纪以来已习以为常的枯燥、繁重工作。这是一件美妙的事，而且，就像“避免”体力劳动一样，我们没有理由不追求“避免”脑力劳动。辛苦的、沉闷的、重复性的劳动对人类创造性是毒药，我们理应尽力避免，而算法恰恰能帮助我们做到这一点。
此外，数字技术如今能成就很多壮举，它并不令人烦乱厌恶，而是符合人性本质。机器识别和合成语音、翻译文章、分类并总结文档、预报天气，都是在大量素材中以不可思议的准确性查找相应的模式、运行其他机器、做数学、在博弈中战胜我们，以及帮助我们发明其他机器。所有这些都是用算法做到的，机器完成这些工作就能让我们少做一些，给予我们时间追求自己的兴趣，甚至给予我们时间和机会发明进一步减少日常工作的更好算法。
算法并非始于计算机时代，从古代开始算法就伴随着我们，当然它也并不局限于计算机科学。我们现在已经很难找到一门完全未被算法改变的学科了。因此，很多人在不知不觉中就接触了算法，他们发现：对于他们的学科而言，算法已经成为一个重要组成部分，尽管这门学科看起来与计算机的距离那么遥远。这样，他们有必要学习算法，以便能理解、使用算法。
即使是一些简单的事情和日常工作，也令人惊讶地在日复一日地浪费着我们的劳动，就是因为我们没有使用一些正确的思想。作者常常看到，人们在日常办公过程中做的一系列操作，其实可以一眨眼就做完，只要他们知道如何避免繁冗的劳作——当然，并不是通过逃避来避免（一些人擅长于此），而是让计算机帮他们做这些事（应该有更多人精于此）。
目标读者
本书的撰写目标是作为算法的第一本入门书籍。如果你是计算机科学专业，可以将本书作为入门书籍，然后继续钻研进阶教材。算法是计算的核心，像本书这样的介绍只是走马观花。
还有很多读者从事其他职业，但意识到算法已成为其职业的必备工具。在很多学科中，几乎不可能不使用算法。本书希望为这样的读者而服务：他们需要使用和理解算法，作为其工作和学习的一部分（哪怕不是核心部分）。有很多读者都是这种情况。
然后就是那些可能要使用算法（无论多么小或多么简单的算法）来简化工作、避免在琐事上浪费时间的读者。需要花费一个勤奋的劳动者数小时时间的任务，很可能用现代脚本语言写的寥寥几行计算机代码瞬间即可完成。有时，一个毫无经验的人突然间顿悟，就能做出如此成绩，因为算法思维并非一些耀眼的专业人士的特权。
要在现代社会中正常生活，基础的数学和科学知识是必需的，这一点恐怕没有人能充分反驳。类似地，不掌握基本的算法知识，也不太可能成为当代社会中有作为的一分子。算法已成为人们日常生活的基础。
读者须知
只有计算机科学家才能理解算法，这种看法是错误的。算法由执行任务的指令组成，所有人都能理解它。但为了更有效地使用算法以及能从像本书这样的书籍中受益，读者应该掌握一些基本技能。
读者不必是一名有经验的数学家，但应能比较顺利地接受一些基本的数学概念和符号描述。本书涉及的数学知识不会超过普通中学所讲授的内容。读者不必了解高等数学，但必须知道怎样证明，因为我们证明算法正确工作的方式与数学证明一样遵循逻辑步骤。这并不意味着在本书中我们会使用大量完整的数学证明，但读者应该理解我们是如何使用证明的。
读者不必是一名熟练的程序员，但应该对计算机的工作原理、如何编写程序以及计算机语言是如何构造的有一个基本理解。我们不要求读者深入理解任何一方面，实际上，最好是在学习算法的过程中阅读本书。计算机系统和算法是密不可分的，两者相互解释。
保持好奇心是必要的。算法是用来高效求解我们遇到的问题的。每当你思考“这是更好的解决方法吗？”，你其实就是在寻找算法。
风格
本书的主旨是令算法尽量简单，避免读者有挫败感。如果你在阅读一本书的时候发现它已超出了你的理解力，那么很可能它不适合你；如果你不理解一本书的内容而对其感到畏惧，那就表明你有了挫败感。我们努力避免本书陷入这样的境地，这需要对介绍的内容进行一定的简化，还意味着我们在呈现某些内容时不能给出其完整的证明。
简化一些内容以及忽略一些复杂的内容并不意味着读者学习本书时就不必积极努力了：这正是我们努力不使读者有挫败感的地方。我们假定读者真的想学习算法，这的确需要努力和