算法图解

巴尔加瓦

前言

我是视觉型学习者，对图解式写作风格钟爱有加。

路线图

遇到问题时，如果不确定该如何高效地解决，可尝试分而治之（第4章）或动态规划（第9章）；如果认识到根本就没有高效的解决方案，可转而使用贪婪算法（第8章）来得到近似答案。

如何阅读本书

强烈建议你动手执行示例代码，这部分的重要性再怎么强调都不过分。可以原封不动地输入代码，也可从www.manning.com/books/grokking-algorithms或https://github.com/egonschiele/grokking_algorithms下载，再执行它们。这样，你记住的内容将多得多。

读者对象

需要重温算法的计算机专业毕业生

代码约定和下载

本书的示例代码可从出版社网站www.manning.com/books/grokking-algorithms下载，也可从https://github.com/egonschiele/grokking_algorithms下载。

1.1 引言

算法是一组完成任务的指令。任何代码片段都可视为算法
该使用合并排序算法还是快速排序算法，或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。
你将学习使用K最近邻算法编写推荐系统；
如果你不懂任何编程语言但想学习一门，请选择Python，它非常适合初学者；

1.2 二分查找

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

1.3 大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。
算法的运行时间以不同的速度增加
简单查找算法编写起来更容易，因此出现bug的可能性更小
有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。
大O表示法计算的是操作数
算法的速度指的并非时间，而是操作数的增速。

1.4 小结

算法运行时间并不以秒为单位。❑ 算法运行时间是从其增速的角度度量的。❑ 算法运行时间用大O表示法表示。

第2章选择排序

学习两种最基本的数据结构——数组和链表，它们无处不在。
必须知道大O表示法和对数

2.1 内存的工作原理

计算机就像是很多抽屉的集合体，每个抽屉都有地址。
需要存储多项数据时，有两种基本方式——数组和链表。

2.2 数组和链表

需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。
有两种访问方式：随机访问和顺序访问。

2.3 选择排序

一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。
选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O(n log n)

2.4 小结

在同一个数组中，所有元素的类型都必须相同（都为int、double等）。

第3章递归

学习如何将问题分成基线条件和递归条件。
请用纸和笔逐步执行至少一个递归函数，就像这样：我使用5来调用factorial，这将使用4调用factorial，并将返回结果乘以5，以此类推。这样逐步执行递归函数可搞明白递归函数的工作原理。
伪代码是对手头问题的简要描述，看着像代码，但其实更接近自然语言。

3.1 递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

3.2 基线条件和递归条件

由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。
每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

3.3 栈

调用栈（call stack）
一叠便条要简单得多：插入的待办事项放在清单的最前面；读取待办事项时，你只读取最上面的那个，并将其删除。因此这个待办事项清单只有两种操作：压入（插入）和弹出（删除并读取）。
计算机在内部使用被称为调用栈的栈。
调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。
每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。

3.4 小结

3.4 小结❑ 递归指的是调用自己的函数。❑ 每个递归函数都有两个条件：基线条件和递归条件。❑ 栈有两种操作：压入和弹出。❑ 所有函数调用都进入调用栈。❑ 调用栈可能很长，这将占用大量的内存。

第4章快速排序

分而治之（divide and conquer, D&C）——一种著名的递归式问题解决方法。

4.1 分而治之

你要将这块地均匀地分成方块，且分出的方块要尽可能大。
使用D&C解决问题的过程包括两个步骤。 (1) 找出基线条件，这种条件必须尽可能简单。 (2) 不断将问题分解（或者说缩小规模），直到符合基线条件。
适用于这小块地的最大方块，也是适用于整块地的最大方块
余下的这块土地满足基线条件，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！
这里重申一下D&C的工作原理：(1) 找出简单的基线条件；(2) 确定如何缩小问题的规模，使其符合基线条件。
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

4.2 快速排序

C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C。
基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。
数组中选择一个元素，这个元素被称为基准值（pivot）。
1) 选择基准值。(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。(3) 对这两个子数组进行快速排序。
归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。

4.3 再谈大O表示法

快速排序的独特之处在于，其速度取决于选择的基准值。
快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。
但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。
在这个示例中，层数为O(log n)（用技术术语说，调用栈的高度为O(log n)），而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) ＊ O(log n)=O(n log n)。这就是最佳情况。

4.4 小结

大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。

第5章散列表

学习散列表的内部机制：实现、冲突和散列函数

5.1 散列函数

散列函数“将输入映射到数字”。
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
散列表由键和值组成。在前面的散列表book中，键为商品名，值为商品价格。散列表将键映射到值。

5.2 应用案例

Python提供了一种创建散列表的快捷方式——使用一对大括号。
这个过程被称为DNS解析（DNS resolution），散列表是提供这种功能的方式之一。
如果“tom”在散列表中，函数get将返回它；否则返回None。你可使用这个函数检查来投票的人是否投过票！
如果你将已投票者的姓名存储在列表中，这个函数的速度终将变得非常慢，因为它必须使用简单查找搜索整个列表。但这里将它们存储在了散列表中，而散列表让你能够迅速知道来投票的人是否投过票。使用散列表来检查是否重复，速度非常快。
这里总结一下，散列表适合用于：❑ 模拟映射关系；❑ 防止重复；❑ 缓存/记住数据，以免服务器再通过处理来生成它们。

5.3 冲突

首先，我撒了一个善意的谎。我之前告诉你的是，散列函数总是将不同的键映射到数组的不同位置。
处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。

5.4 性能

而要避免冲突，需要有：❑ 较低的填装因子；❑ 良好的散列函数。
散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数
一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

5.5 小结

❑ 你可以结合散列函数和数组来创建散列表。 ❑ 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。 ❑ 散列表的查找、插入和删除速度都非常快。 ❑ 散列表适合用于模拟映射关系。 ❑ 一旦填装因子超过0.7，就该调整散列表的长度。 ❑ 散列表可用于缓存数据（例如，在Web服务器上）。 ❑ 散列表非常适合用于防止重复。

第6章广度优先搜索

学习广度优先搜索，你可对图使用这种算法回答诸如“到X的最短路径是什么”等问题。
广度优先搜索让你能够找出两样东西之间的最短距离

6.1 图简介

解决最短路径问题的算法被称为广度优先搜索。

6.2 图是什么

图由节点（node）和边（edge）组成。
图用于模拟不同的东西是如何相连的。

6.3 广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。 ❑ 第一类问题：从节点A出发，有前往节点B的路径吗？ ❑ 第二类问题：从节点A出发，前往节点B的哪条路径最短？
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。
队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。
队列是一种先进先出（First In First Out, FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。

6.4 实现图

散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。

6.5 实现算法

先概述一下这种算法的工作原理。
在Python中，可使用函数deque来创建一个双端队列。
这个函数检查人的姓名是否以m结尾
检查完一个人后，应将其标记为已检查，且不再检查他
检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个列表来记录检查过的人。
广度优先搜索的运行时间为O(人数+边数)，这通常写作O(V+E)，其中V为顶点（vertice）数，E为边数。
如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。
树是一种特殊的图，其中没有往后指的边。

6.6 小结

你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。❑ 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

第7章狄克斯特拉算法

介绍狄克斯特拉算法，让你能够找出加权图中前往X的最短路径。

7.1 使用狄克斯特拉算法

狄克斯特拉算法包含4个步骤。 (1) 找出“最便宜”的节点，即可在最短时间内到达的节点。 (2) 更新该节点的邻居的开销，其含义将稍后介绍。 (3) 重复这个过程，直到对图中的每个节点都这样做了。 (4) 计算最终路径。
对于节点B的邻居，如果找到前往它的更短路径，就更新其开销。
你对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。
如果使用广度优先搜索，找到的最短路径将不是这条，因为这条路径包含3段，而有一条从起点到终点的路径只有两段。
狄克斯特拉算法包含4个步骤。 (1) 找出最便宜的节点，即可在最短时间内前往的节点。 (2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。 (3) 重复这个过程，直到对图中的每个节点都这样做了。 (4) 计算最终路径。

7.2 术语

要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。
狄克斯特拉算法只适用于有向无环图（directed acyclic graph, DAG）。

7.3 换钢琴

为计算最终路径，还需在这个表中添加表示父节点的列。
这就是狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径！
下一个最便宜的是吉他，因此更新其邻居的开销
通过沿父节点回溯，便得到了完整的交换路径。
最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。

7.4 负权边

从黑胶唱片到海报的边的权重为负！
如果有负权边，就不能使用狄克斯特拉算法。
根据狄克斯特拉算法，没有比不支付任何费用获得海报更便宜的方式。（你知道这并不对！）
海报节点已处理过，这里却更新了它的开销。这是一个危险信号。节点一旦被处理，就意味着没有前往该节点的更便宜途径，但你刚才却找到了前往海报节点的更便宜途径！
在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Fordalgorithm）。

7.5 实现

节点的开销指的是从起点出发前往该节点需要多长时间
这就是实现狄克斯特拉算法的Python代码！
开销指的是从起点前往该节点需要多长时间。

7.6 小结

❑ 广度优先搜索用于在非加权图中查找最短路径。❑ 狄克斯特拉算法用于在加权图中查找最短路径。❑ 仅当权重为正时狄克斯特拉算法才管用。❑ 如果图中包含负权边，请使用贝尔曼-福德算法。

第8章贪婪算法

学习如何处理不可能完成的任务：没有快速算法的问题（NP完全问题）。

8.1 教室调度问题

(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。

8.2 背包问题

在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

8.3 集合覆盖问题

列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2n个。
在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：❑ 速度有多快；❑ 得到的近似解与最优解的接近程度。
集合类似于列表，只是同样的元素只能出现一次，即集合不能包含重复的元素。
其中的键为广播台的名称，值为广播台覆盖的州
states_covered是一个集合，包含该广播台覆盖的所有未覆盖的州
❑ 集合类似于列表，只是不能包含重复的元素；❑ 你可执行一些有趣的集合运算，如并集、交集和差集。

8.4 NP完全问题

因此涉及3个城市时，可能的路线有6条。
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。
NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。
❑ 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。 ❑ 涉及“所有组合”的问题通常是NP完全问题。 ❑ 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。 ❑ 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。 ❑ 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。 ❑ 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

8.5 小结

❑ 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。 ❑ 对于NP完全问题，还没有找到快速解决方案。 ❑ 面临NP完全问题时，最佳的做法是使用近似算法。 ❑ 贪婪算法易于实现、运行速度快，是不错的近似算法。

第9章动态规划

这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题

9.1 背包问题

最简单的算法如下：尝试各种可能的商品组合，并找出价值最高的组合。
动态规划先解决子问题，再逐步解决大问题。
每个动态规划算法都从一个网格开始
动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。
在每一行，可偷的商品都为当前行的商品以及之前各行的商品。
在1磅的容量中，可装入的商品的最大价值是多少呢？
余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品

9.2 背包问题FAQ

每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低！
使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。
这也是一个背包问题！但约束条件不是背包的容量，而是有限的时间；不是决定该装入哪些商品，而是决定该去游览哪些名胜。
但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

9.3 最长公共子串

在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
❑ 单元格中的值是什么？❑ 如何将这个问题划分为子问题？❑ 网格的坐标轴是什么？
费曼算法（Feynman algorithm）。这个算法是以著名物理学家理查德·费曼命名的，其步骤如下。(1) 将问题写下来。(2) 好好思考。(3) 将答案写下来。
但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。
这里比较的是最长公共子串，但其实应比较最长公共子序列：两个单词中都有的序列包含的字母数。
你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。

9.4 小结

❑ 需要在给定约束条件下优化某种指标时，动态规划很有用。 ❑ 问题可分解为离散子问题时，可使用动态规划来解决。 ❑ 每种动态规划解决方案都涉及网格。 ❑ 单元格中的值通常就是你要优化的值。 ❑ 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。 ❑ 没有放之四海皆准的计算动态规划解决方案的公式。

10.1 橙子还是柚子

K最近邻（k-nearest neighbours, KNN）算法进行了分类

10.2 创建推荐系统

要计算两点的距离，可使用毕达哥拉斯公式。
下面是一种将用户转换为一组数字的方式。用户注册时，要求他们指出对各种电影的喜欢程度。这样，对于每位用户，都将获得一组数字！
在数学家看来，这里计算的是五维（而不是二维）空间中的距离，但计算公式不变。
你将使用KNN来做两项基本工作——分类和回归： ❑ 分类就是编组； ❑ 回归就是预测结果（如一个数字）。
余弦相似度（cosine similarity）。
使用KNN时，挑选合适的特征进行比较至关重要。所谓合适的特征，就是： ❑ 与要推荐的电影紧密相关的特征； ❑ 不偏不倚的特征（例如，如果只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）。
在挑选合适的特征方面，没有放之四海皆准的法则，你必须考虑到各种需要考虑的因素。

10.3 机器学习简介

KNN算法真的是很有用，堪称你进入神奇的机器学习领域的领路人！
OCR指的是光学字符识别（optical character recognition）
垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（Naive Bayes classifier）

10.4 小结

❑ KNN用于分类和回归，需要考虑最近的邻居。 ❑ 分类就是编组。 ❑ 回归就是预测结果（如数字）。 ❑ 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。 ❑ 能否挑选合适的特征事关KNN算法的成败。

11.1 树

有人设计了一种名为二叉查找树（binary search tree）的数据结构。
对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。
如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆，伸展树。

11.2 反向索引

一个散列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（inverted index），常用于创建搜索引擎。

11.3 傅里叶变换

Better Explained是一个杰出的网站，致力于以通俗易懂的语言阐释数学，它就傅里叶变换做了一个绝佳的比喻：给它一杯冰沙，它能告诉你其中包含哪些成分。

11.4 并行算法

负载均衡。

11.5 MapReduce

分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。

11.6 布隆过滤器和HyperLogLog

11.6 布隆过滤器和HyperLogLog
布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。

11.7 SHA算法

另一种散列函数是安全散列算法（secure hash algorithm, SHA）函数。给定一个字符串，SHA返回其散列值。
你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。
当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。

11.8 局部敏感的散列算法

希望散列函数是局部敏感的。在这种情况下，可使用Simhash。如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度，这很有用！

11.9 Diffie-Hellman密钥交换

这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息进行加密，以便只有收件人才能看懂呢？
Diffie-Hellman使用两个密钥：公钥和私钥。

11.10 线性规划

线性规划用于在给定约束条件下最大限度地改善指定的指标。
线性规划使用Simplex算法

11.11 结语

最佳的学习方式是找到感兴趣的主题，然后一头扎进去

练习答案

栈将不断地增大。每个程序可使用的调用栈空间都有限，程序用完这些空间（终将如此）后，将因栈溢出而终止。