内 容 提 要 本书示例丰富，图文并茂，以简明易懂的方式阐释了算法，旨在帮助程序员在日常项目中更好地利用 算法为软件开发助力。前三章介绍算法基础，包括二分查找、大 O 表示法、两种基本的数据结构以及递归 等。余下的篇幅将主要介绍应用广泛的算法，具体内容包括 ：面对具体问题时的解决技巧，比如何时采用 贪婪算法或动态规划 ；散列表的应用 ；图算法 ；K 最近邻算法。 本书适合所有程序员、计算机专业相关师生以及对算法感兴趣的读者。 [美] Aditya Bhargava 译 袁国忠 责任编辑 朱 巍 执行编辑 贺子娟 责任印制 彭志环 ◆ 人民邮电出版社出版发行 北京市丰台区成寿寺路11号 ◆ 著 邮编 100164 网址 http://www.ptpress.com.cn 北京 电子邮件 [email protected] 印刷 ◆ 开本：800×1000 1/16 印张：12.25 字数：308千字 印数：1 — 4 000册 著作权合同登记号 2017年 3 月第 1 版 2017年 3 月北京第 1 次印刷 图字：01-2016-5339号 定价：49.00元 读者服务热线：(010)51095186转600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广字第 8052 号 4 献 词 谨以此书献给我的父母、Sangeeta和Yogesh 前 言 1 1 前 言 2 3 我因为爱好而踏入了编程殿堂。Visual Basic 6 for Dummies教会了我基础知识，接着我不断阅 读，学到的知识也越来越多，但对算法却始终没搞明白。至今我还记得购买第一本算法书后的情 景：我琢磨着目录，心想终于要把这些主题搞明白了。但那本书深奥难懂，看了几周后我就放弃 了。直到遇到一位优秀的算法教授后，我才认识到这些概念是多么地简单而优雅。 几年前，我撰写了第一篇图解式博文。我是视觉型学习者，对图解式写作风格钟爱有加。从 那时候起，我撰写了多篇介绍函数式编程、Git、机器学习和并发的图解式博文。顺便说一句， 刚开始我的写作水平很一般。诠释技术概念很难，设计出好的示例需要时间，阐释难以理解的概 念也需要时间，因此很容易对难讲的内容一带而过。我本以为自己已经做得相当好了，直到有一 篇博文大受欢迎，有位同事却跑过来跟我说：“我读了你的博文，但还是没搞懂。 ”看来在写作方 面我要学习的还有很多。 在撰写这些博文期间，Manning出版社找到我，问我想不想编写一本图解式图书。事实证明， Manning出版社的编辑对如何诠释技术概念很在行，他们教会了我如何做。我编写本书的目的就 是要把难懂的技术主题说清楚，让这本算法书易于理解。与撰写第一篇博文时相比，我的写作水 平有了长足进步，但愿你也认为本书内容丰富、易于理解。 4 5 6 7 8 9 10 11 12 13 6 前 言 致 谢 感谢Manning出版社给我编写本书的机会，并给予我极大的创作空间。感谢出版人Marjan Bace，感谢Mike Stephens领我入门，感谢Bert Bates教我如何写作，感谢Jennifer Stout的快速回复 以及大有帮助的编辑工作。感谢Manning出版社的制作人员，他们是Kevin Sullivan、Mary Piergies、 Tiffany Taylor、Leslie Haimes以及其他幕后人员。另外，还要感谢阅读手稿并提出建议的众人， 他们是Karen Bensdon、Rob Green、Michael Hamrah、Ozren Harlovic、Colin Hastie、Christopher Haupt、 Chuck Henderson、Pawel Kozlowski、Amit Lamba、Jean-Francois Morin、Robert Morrison、Sankar Ramanathan、Sander Rossel、Doug Sparling和Damien White。 感谢一路上向我伸出援手的人：Flaskhit游戏专区的各位教会了我如何编写代码；很多朋友 帮助审阅手稿、提出建议并让我尝试不同的诠释方式，其中包括Ben Vinegar、Karl Puzon、Alex Manning、Esther Chan、Anish Bhatt、Michael Glass、Nikrad Mahdi、Charles Lee、Jared Friedman、 Hema Manickavasagam、Hari Raja、Murali Gudipati、Srinivas Varadan等；Gerry Brady教会了我算 法。还要深深地感谢算法方面的学者，如CLRS①、高德纳和Strang。我真的是站在了巨人的肩上。 感谢爸爸、妈妈、Priyanka和其他家庭成员，感谢你们一贯的支持。深深感谢妻子Maggie， 我们的面前还有很多艰难险阻，有些可不像周五晚上待在家里修改手稿那么简单。 最后，感谢所有试读本书的读者，还有在论坛上提供反馈的读者，你们让本书的质量更上了 一层楼。 —————————— ① 《算法导论》四位作者的姓氏（Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein）首字 母缩写。——译者注 关于本书 1 1 关于本书 2 3 本书易于理解，没有大跨度的思维跳跃，每次引入新概念时，都立即进行诠释，或者指出将 在什么地方进行诠释。核心概念都通过练习和反复诠释进行强化，以便你检验假设，跟上步伐。 书中使用示例来帮助理解。我的目标是让你轻松地理解这些概念，而不是让正文充斥各种符 号。我还认为，如果能够回忆起熟悉的情形，学习效果将达到最佳，而示例有助于唤醒记忆。因 此，如果你要记住数组和链表（第2章）之间的差别，只要想想在电影院找座位就坐的情形。另 外，不怕你说我啰嗦，我是视觉型学习者，因此本书包含大量的图示。 本书内容是精挑细选的。没必要在一本书中介绍所有的排序算法，不然还要维基百科和可汗 学院做什么。书中介绍的所有算法都非常实用，对我从事的软件工程师的工作大有帮助，还可为 阅读更复杂的主题打下坚实的基础。祝你阅读愉快！ 4 5 6 7 路线图 本书前三章将帮助你打好基础。 8  第1章：你将学习第一种实用算法——二分查找；还将学习使用大O表示法分析算法的速 度。本书从始至终都将使用大O表示法来分析算法的速度。  第2章：你将学习两种基本的数据结构——数组和链表。这两种数据结构贯穿本书，它们 还被用来创建更高级的数据结构，如第5章介绍的散列表。  第3章：你将学习递归，一种被众多算法（如第4章介绍的快速排序）采用的实用技巧。 根据我的经验，大O表示法和递归对初学者来说颇具挑战性，因此介绍这些内容时我放慢了 脚步，花费的篇幅也较长。 余下的篇幅将介绍应用广泛的算法。  问题解决技巧：将在第4、8和9章介绍。遇到问题时，如果不确定该如何高效地解决，可 尝试分而治之（第4章）或动态规划（第9章）；如果认识到根本就没有高效的解决方案， 可转而使用贪婪算法（第8章）来得到近似答案。  散列表：将在第5章介绍。散列表是一种很有用的数据结构，由键值对组成，如人名和电 9 10 11 12 13 2 关于本书 子邮件地址或者用户名和密码。散列表的用途之大，再怎么强调都不过分。每当我需要 解决问题时，首先想到的两种方法是：可以使用散列表吗？可以使用图来建立模型吗？  图算法：将在第6、7章介绍。图是一种模拟网络的方法，这种网络包括人际关系网、公 路网、神经元网络或者任何一组连接。广度优先搜索（第6章）和狄克斯特拉算法（第7 章）计算网络中两点之间的最短距离，可用来计算两人之间的分隔度或前往目的地的最 短路径。  K最近邻算法（KNN） ：将在第10章介绍。这是一种简单的机器学习算法，可用于创建推 荐系统、OCR引擎、预测股价或其他值（如“我们认为Adit会给这部电影打4星”）的系统， 以及对物件进行分类（如“这个字母是Q”） 。  接下来如何做：第11章概述了适合你进一步学习的10种算法。 如何阅读本书 本书的内容和排列顺序都经过了细心编排。如果你对某个主题感兴趣，直接跳到那里阅读即 可；否则就按顺序逐章阅读吧，因为它们都以之前介绍的内容为基础。 强烈建议你动手执行示例代码，这部分的重要性再怎么强调都不过分。可以原封不动地输入 代码，也可从www.manning.com/books/grokking-algorithms或https://github.com/egonschiele/grokking_ algorithms下载，再执行它们。这样，你记住的内容将多得多。 另外，建议你完成书中的练习。这些练习都很短，通常只需一两分钟就能完成，但有些可能 需要5~10分钟。这些练习有助于检查你的思路，以免偏离正道太远。 读者对象 本书适合任何具备编程基础并想理解算法的人阅读。你可能面临一个编程问题，需要找一种 算法来实现解决方案，抑或你想知道哪些算法比较有用。下面列出了可能从本书获得很多帮助的 部分读者。  业余程序员  编程培训班学员  需要重温算法的计算机专业毕业生  对编程感兴趣的物理或数学等专业毕业生 代码约定和下载 本书所有的示例代码都是使用Python 2.7编写的。书中在列出代码时使用了等宽字体。有些 代码还进行了标注，旨在突出重要的概念。 关于本书 3 本书的示例代码可从出版社网站www.manning.com/books/grokking-algorithms下载，也可从 https://github.com/egonschiele/grokking_algorithms下载。 1 我认为，如果能享受学习过程，就能获得最好的学习效果。请尽情地享受学习过程，动手运 行示例代码吧！ 2 作者在线 购买英文版的读者可免费访问Manning出版社管理的专用网络论坛，并可以评论本书、提出 技术性问题以及获得作者和其他读者的帮助。若要访问并订阅该论坛，可在浏览器的地址栏中输 入www.manning.com/books/grokking-algorithms。这个网页会告诉你注册后如何进入论坛、可获得 哪些帮助以及讨论时应遵守的规则。 Manning出版社致力于为读者和作者提供能够深入交流的场所。然而，作者参与论坛讨论纯 属自愿，没有任何报酬，因此Manning出版社对其参与讨论的程度不做任何承诺。建议你向作者 提些有挑战性的问题，以免他失去参与讨论的兴趣！只要本书还在