《算法图解》笔记

7月份的时候看完这本算法入门书，学习难度比较低，很快就看完了。但是时隔两个月再回想，书中的内容已经了无印象，今天重拾本书，顺便做些笔记加深印象。
整本书的结构是穿插着介绍了数据结构和算法，以及大 O 表示法。但是有些部分讲的有些过于简单了，如果不是看了极客时间的「数据结构与算法之美」课程 ，可能理解起来还会吃力，尤其合并排序与快速排序的比较，写得那叫一个草率，所以这本书就是个入门书，深入学习还是得另辟蹊径。

笔记分成 3 部分 ：

1. 大 O 表示法
2. 数据结构 : 数组、链表、栈、散列表、队列、图
3. 算法 : 二分查找、选择排序、递归、快速排序、广度优先搜索、狄克斯特拉算法、贪婪算法、动态规划、K 最近邻算法、其他

一、大 O 表示法

书中主要用大 O 表示法来说明了算法的时间复杂度，但是并不是时间复杂度最优的算法就是最优算法，在实际应用中还要综合考虑到空间的复杂度，两者综合起来才能选择出更合适的算法。

从快到慢常见的 5 种时间复杂度如下：

• 1. O(log n)，也叫对数时间，这样的算法包括二分查找。
• 2. O(n)，也叫线性时间，这样的算法包括简单查找。
• 3. O(n * log n)，一种速度较快的排序算法，如：快速排序、合并排序。
• 4. O(n²)，一种速度较慢的排序算法，如：选择排序。
• 5. O(n!)，一种非常慢的算法，如：旅行商问题的解决方案。

当需要处理的数据量不断变大时，各种算法所需的时间呈现不同量级的增长，如下图所示：

大O表示法.jpeg

二、数据结构

2.1 数组 & 链表

需要存储多个元素时，可使用数组或链表。使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。需要同时读取所有元素时，链表的效率很高；需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。

数组的特性：

• 数组的元素都在一起。
• 数组的读取速度很快。
• 在同一个数组中，所有元素的类型都必须相同(都为int、double等)。

链表的特性：

• 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
• 链表的插入和删除速度很快。

数组 & 链表各个操作的运行时间如下图：

数组与链表.jpeg

2.2 栈

• 栈是一种简单的数据结构，栈有两种操作：压入（插入）和弹出（删除并读取）。
• 所有函数调用都进入调用栈。
• 调用栈可能很长，这将占用大量的内存。

调用栈： 每当调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。这个栈用于存储多个函数的变量，被称为调用栈。

2.3 散列表

2.3.1 散列函数

散列函数是这样一种函数：无论你给他什么数据，他都还你一个数字。即“将输入映射到数字”，散列函数必须满足一些要求：

• 它必须是一致的，即每次同样的输入都会得到同样的输出结果
• 它应将不同的输入映射到不同的数字

2.3.2 散列函数可以精准的指出 XX 元素的存储位置，根本不用查找，因为：

1. 散列函数总是将同样的输入映射到相同的索引。 
2. 散列函数将不同的输入映射到不同的索引。 
3. 散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。

2.3.3 散列表

结合散列函数和数组可以创建一种叫做「散列表」的数据结构。数组和链表都被直接映射到内存，但散列表更复杂一些，它使用散列函数来确定元素的存储位置。散列表也被称为散列映射、映射、字典和关联数组。散列表也使用数组来存储数据，因此其获取元素的速度与数组一样快。
散列表适合用于：

1. 模拟映射关系； 
2. 防止重复； 
3. 缓存/记住数据，以免服务器再通过处理来生成它们。

2.3.4 散列函数的时间复杂度

在平均情况下，散列表执行各种操作的时间都为O(1)。 O(1)被称为常量时间。简单查找的运行时间为线性时间。二分查找的速度更快，所需时间为对数时间。在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。
在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。
因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

• 较低的填装因子；
• 良好的散列函数。

2.3.5 总结：散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。

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

2.4 队列

• 队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作： 入队和出队。
• 队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。

2.5 图

• 图模拟一组连接
• 图由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居
• 图有：有向图和无向图，以边是否带箭头区分
• 加权图：提高或者降低某些边的权重，可以是负权值

三、算法

3.1 二分查找

• 二分查找是一种算法，其输入是一个有序的元素列表，如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
• 使用二分查找时，每次都排除一半的数字。
• 一般而言，对于包含n个元素的列表，用二分查找最多需要（log n）步，而简单查找最多需要 n 步。

注意：仅当列表是有序的时候，二分查找才有用。

3.2 选择排序

• 选择排序（Selection sort）是一种简单直观的排序算法。
• 它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。需要的总时间为 O(n × n)，即 O(n²)。
• 选择排序是不稳定的排序方法，主要是在有重复元素的情况下。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了。

3.3 递归

• 程序调用自身的编程技巧称为递归（ recursion）。
• 每个递归函数都有两部分：基线条件（ base case）和递归条件（ recursive case） 。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
• 递归只是为了让解决方案更清晰，但并不一定性能更好。「如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。」

3.4 快速排序

• 快速排序是一种分而治之（divide and conquer，D&C）算法，是一种著名的递归式问题解决办法。
• 快速排序的平均运行时间为 O(n * log n)。

3.4.1 D&C 算法的工作原理：

1. 找出简单的基线条件；
2. 确定如何缩小问题的规模，使其符合基线条件。

提示：编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

3.4.2 快速排序两大优势：

1. 快速排序是原地排序（只需要非常小的一个辅助栈）
2. 快速排序时间消耗，长度为N的数组排序时间与NlgN成正比

3.4.3 合并排序，或者叫归并排序

• 合并排序也是建立在归并操作上的一种有效的排序算法。也是采用分治法的一个非常典型的应用。
• 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序与快排的对比图

归并&快排-来自极客时间.jpg

归并排序的时间复杂度任何情况下都是 O(n*log n)，但并不如快排应用广泛，因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间，也就是说它不是原地排序算法。

3.4.4 大O表示法中的常量

• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。

3.5 广度优先搜索

广度优先搜索让你能够找出两样东西之间的最短距离，广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：

1. 第一类问题:从节点A出发，有前往节点B的路径吗?
2. 第二类问题:从节点A出发，前往节点B的哪条路径最短?

小结

• 广度优先搜索指出是否有从A到B的路径。
• 如果有，广度优先搜索将找出最短路径。
• 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。
• 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。
• 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约会，而rachel也与ross约会”。
• 队列是先进先出(FIFO)的。
• 栈是后进先出(LIFO)的。
• 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
• 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

3.6 狄克斯特拉算法

• 要计算非加权图中的最短路径，可使用广度优先搜索。
• 要计算加权图中的最短路径，可使用狄克斯特拉算法。狄克斯特拉算法只适用于有向无环图（DAG）。
• 最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。
• 如果图中包含负权边，请使用贝尔曼-福德算法。

狄克斯特拉算法的4个步骤：

1. 找出“最便宜”的节点，即可在最短时间内到达的节点。
2. 更新该节点的邻居的开销，其含义将稍后介绍。
3. 重复这个过程，直到对图中的每个节点都这样做了。
4. 计算最终路径。

3.7 贪婪算法

• 贪婪算法很简单：每步都采取最优的做法。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。
• 贪婪算法是一种 NP 完全问题的近似解。

NP完全问题的简单定义是，以难解著称的问题.它们一般有如下特征：

• 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
• 涉及“所有组合”的问题通常是NP完全问题。
• 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
• 如果问题涉及序列(如旅行商问题中的城市序列)且难以解决，它可能就是NP完全问题。
• 如果问题涉及集合(如广播台集合)且难以解决，它可能就是NP完全问题。
• 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

3.8 动态规划

• 动态规划先解决子问题，再逐步解决大问题。
• 动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。 但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

设计动态规划方案的小贴士：

• 每种动态规划解决方案都涉及网格。
• 单元格中的值通常就是你要优化的值。
• 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题，这有助于你找出网格的坐标轴。

费曼算法(Feynman algorithm)步骤如下：

1. 将问题写下来。
2. 好好思考。
3. 将答案写下来。

3.9 K 最近邻算法（KNN）

KNN(K-nearest neighbours)可以用来做两项基本工作——分类和回归：

1. 分类就是编组；
2. 回归就是预测结果（如一个数字）。

KNN 算法使用场景：

1. OCR（ optical character recognition），光学字符识别
2. 创建垃圾邮件过滤器
3. 预测股票市场

小结

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

3.10 其他

简单提及了10个作者认为打算深入学习者进一步可以选择的学习内容和方向。

1. 树（B树、红黑树、堆、伸展树）；
2. 反向索引（inverted index）；
3. 傅立叶变换（非常适合用于处理信号）；
4. 并行算法，速度并不是线性的，会受到并行性管理开销和负载均衡的影响；
5. MapReduce 分布式算法（映射和归并，映射是将一个数组转换为另一个数组，归并是将一个数组转换为一个元素）；
6. 布隆过滤器（概率型数据结构，使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的）和HyperLogLog（一种类似于布隆过滤器的算法）；
7. SHA(secure hash algorithm)算法（安全散列算法函数，一个散列函数，它生成一个散列值：一个较短的字符串）；
8. 局部敏感的散列算法，如：Simhash。（SHA算法局部不敏感）；
9. Diffie-Hellman密匙交换：非对称加密。（Diffie-Hellman算法解决了如下两个问题： 1. 双方无需知道加密算法。他们不必会面协商要使用的加密算法。2. 要破解加密的消息比登天还难。）
10. 线性规划，使用Simplex算法。