下载掌阅APP，畅读海量书库
立即打开
谈及为什么需要花时间学算法，我至少可以列举出三个很好的理由。
（1）性能：选择正确的算法可以显著提升应用程序的速度。仅就搜索来说，用二分查找替换线性搜索就能为我们带来巨大的收益。
（2）安全性：如果你选用了错误的算法，攻击者就可以利用它使你的服务器、节点或应用程序崩溃。比如哈希碰撞拒绝服务攻击，就利用了作为字典来存放POST请求以提交参数的哈希表，并使用有可能导致大量碰撞的序列来让这个哈希表退化，进而使整个服务器停止响应。另一个关于安全性的有趣例子是，曾有黑客成功使用有缺陷的随机数生成器入侵在线扑克网站。 [1]
[1] “How we learned to cheat at online poker: A study in software security”（“在线扑克如何作弊：一次软件安全研究”），Brad Arkin等，developer.com期刊，1999年。
（3）设计代码的效率：如果有合适的构建模块可用来完成各种事情（特别是如果还能重用代码的话），你就能更快地实现代码的编写，而且会让代码更整洁。
那么，为什么推荐你阅读本书呢？一个很重要的原因就是，在本书中，我精挑细选地为你准备了一个具有战略意义的“高级算法库”，其中的算法能够帮助你改进代码，进而应对现代系统面临的各种挑战。
此外，我试着用一种不同于普通教材的方法来介绍这些算法。虽然本书也会解释算法背后的理论，但更侧重于给出使用这些算法的实际应用程序的相关背景信息，以及在什么时候应该使用这些算法的建议。
在日常工作中，你通常要做的是处理某个大型软件（也可能是遗留软件）上的某个特定部分。但是，在整个职业生涯中，你肯定会遇到需要设计大型软件的情况。到了那时，你就会用上本书讨论的大部分内容了。我将尽可能地给出有关如何编写简洁且高效代码的建议，以帮助你解决将来要面对的相关问题。
正是因为采用了这 种新的方式来介绍算法，所以在每一章中，我都会列举有助于解决某些问题的数据结构。这是一本当你需要用以提高应用程序性能的建议时，可以随时参考的辅助性手册。
最后要说的是，如果你碰巧读过Aditya Y. Bhargava撰写的《算法图解》（人民邮电出版社，2017年），并且十分喜欢里面的内容；那么只要你还想继续学习算法，就可以通过阅读《高级算法和数据结构》得到进一步提升。如果你还没有读过《算法图解》，我强烈推荐你看一看，这本书是你了解算法相关主题的绝佳选择，它能广受欢迎绝非偶然。希望我的这本书也能达到同样的效果。
本书的大部分章节是为对算法、编程和数学已有一些基本了解的读者编写的。如果你想复习一下这些基本内容或者希望快速了解这部分知识，请参阅本书的附录部分。
如果你事先熟悉了如下概念，则可以更好地掌握本书的内容。
●良好的数学和代数基础，大 O 符号（见附录B）以及渐近分析的相关内容。
●简单的数据结构。
●附录C中的概念。
❏ 基本的像数组和链表这样的存储结构。
❏ 哈希表和哈希算法。
❏ 树。
❏ 容器（队列和堆栈）。
❏ 递归的基本概念。
第1章定义了算法和数据结构，阐释了它们的区别，并通过一个例子探究了用不同算法解决问题的过程，以及如何利用这些算法来找到更好的解决方案。
从第2章开始，本书剩余的内容将分为三大部分以及附录。每一部分会集中介绍一大类内容——可以是某个抽象的目标，也可以是我们需要解决的某类问题。
第一部分探讨了一些高级数据结构，目的是让你进一步掌握像跟踪一个或一组事物这样的基本操作。这一部分旨在让你熟悉这样一种思维模式：对数据执行操作的方法有很多，而最好的方法取决于上下文和需求。
第2章介绍了二叉堆的高级变体—— d 叉堆，还描述了第一部分各章中用来介绍各种主题的编撰结构。
第3章利用树堆进一步探讨了堆的高级用法。树堆是二叉搜索树和堆的混合体，可以在不同的上下文中提供帮助。
第4章介绍了布隆过滤器。这是哈希表的一种高级形式，可以帮助我们节省内存，同时将查找操作的平摊时间复杂度维持在常数级别。
第5章介绍了一些用来跟踪不交集的替代数据结构。不交集是构建高级算法的基石，已用在若干实际应用中。
第6章介绍了两种在存储和查找字符串方面都优于通用容器的数据结构：trie（前缀树）和基数树（又称为压缩前缀树）。
第7章基于前面介绍的数据结构构建了一种能有效处理缓存的组合数据结构：LRU缓存，还详细讨论了LFU缓存（LRU缓存的变体）以及如何在多线程环境中同步共享容器的问题。
第二部分探讨搜索算法的一种特殊情况：处理多维数据时应该如何索引这些数据，以及如何执行空间查询。本书将再次展示一些比使用基本搜索算法有更大改进的专用数据结构。不仅如此，这一部分还将描述另一个重要的主题——聚类。聚类用到了大量的空间查询，还用到了MapReduce这样的分布式计算模型。
第8章探讨了最近邻问题。
第9章描述了 k - d 树—— 一种支持在多维数据集上进行高效搜索的解决方案。
第10章介绍了树的更多高级版本，如SS树和R树。
第11章深入探讨了如何基于需要派送的客户地址找到最近的仓库，还着重介绍了最近邻搜索的应用。
第12章介绍了三种旨在高效实现最近邻搜索的聚类算法： k 均值算法、DBSCAN算法和OPTICS算法。
第13章介绍了MapReduce（一种强大的分布式计算模型），并探讨了如何将其应用到第12章所讨论的聚类算法上。
第三部分只关注一种数据结构——图。这部分内容将介绍各种旨在推动当今人工智能和大数据发展的算法。
第14章介绍了图数据结构的基础知识，还介绍了深度优先遍历（DFS）、广度优先遍历（BFS）、迪杰斯特拉算法以及A*算法，并描述了如何使用它们来解决“最短路径”问题。
第15章介绍了图嵌入、平面性以及稍后几章将要尝试解决的几个问题，例如如何找到对图进行嵌入时的最小交叉数，以及如何更好地绘制图。
第16章描述了一种我们在机器学习中经常要用到的基本算法——梯度下降算法，并展示了如何将这种算法应用于图以及图嵌入。
第17章在第16章的基础上介绍了模拟退火算法——这是一种更强大的优化技术。在处理不可微函数或是具有多个局部最小值的函数时，这种算法能够克服梯度下降算法的缺点。
第18章描述了遗传算法——这是一种十分高级的优化技术，有助于加快收敛速度。
本书各章会按照“提出问题→设计数据结构作为解决方案→实现解决方案并分析运行时间和内存需求”这一结构来安排内容。
最后，附录部分涵盖了阅读本书所必须掌握的那些关键主题。附录不是基于示例来讲解的，而是采用了与正文不同的内容组织方式。附录旨在向读者提供在开始阅读正文之前就应该熟悉的各种知识的摘要，其中的大部分主题是基础算法课程中的内容。我们建议读者在阅读第2章之前浏览一遍附录中的内容。
附录A介绍了用来描述算法的伪代码的各种符号。
附录B提供了对大O符号以及时间分析与空间分析的总结。
附录C和附录D给出了各种核心数据结构的摘要。这些数据结构是本书将要介绍的各种高级数据结构的基础模块。
附录E解释了递归。递归是一种比较具有挑战性的编程技术，旨在对算法进行更明确、更简洁的定义。当然，在采用递归时，我们需要对利弊进行权衡。
附录F给出了不同类型的随机算法的定义，包括蒙特卡罗算法、拉斯维加斯算法，还介绍了各种分类问题和随机解决方案的评估指标。
本书中的算法是用伪代码加以解释的，因此读者不需要有特定编程语言的背景知识。
不过，我们还是希望读者对基本的、与语言无关的编程概念有一定的了解，例如循环、条件、布尔运算符、变量以及赋值的相关概念。
附录A提供了一份简短的指南，对本书用到的语法（或者更确切地说，伪语法）进行了介绍。我们建议读者能够在开始阅读第1章之前浏览一遍附录A。当然，如果你对自己非常有信心，可以直接阅读正文中的代码，当觉得对其中使用的语法不甚了解时，再参考附录A中的内容。
本书给出了伪代码，如果你对特定的编程语言感兴趣，或者想要弄清楚书中的概念是如何用真实的可执行代码来实现的，可访问本书的GitHub仓库，以了解如何使用不同的编程语言（如Java、Python、JavaScript）实现本书介绍的各种数据结构。