《算法图解》读书笔记

出版社：人民邮电出版社

出版日期: 2017-3

片段

  • 一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

  • 你可能不记得什么是对数了，但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个：10 × 10 = 100。因此，log10100 = 2。对数运算是幂运算的逆运算。

  • 大O表示法是一种特殊的表示法，指出了算法的速度有多快。

  • 大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

  • 大O表示法指出了最糟情况下的运行时间

  • O(log n)，也叫对数时间，这样的算法包括二分查找。 O(n)，也叫线性时间，这样的算法包括简单查找。 O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

  • 算法的速度指的并非时间，而是操作数的增速。 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。 算法的运行时间用大O表示法表示。 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

  • 二分查找的速度比简单查找快得多。 O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。 算法运行时间并不以秒为单位。 算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示。

  • 需要将数据存储到内存时，你请求计算机提供存储空间，计算机给你一个存储地址。需要存储多项数据时，有两种基本方式——数组和链表。

  • 使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。

  • 链表中的元素可存储在内存的任何地方。

  • 数组用得很多，因为它支持随机访问。有两种访问方式：随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快，这是因为它们支持随机访问。很多情况都要求能够随机访问，因此数组用得很多。

  • 链表擅长插入和删除，而数组擅长随机访问。

  • 计算机内存犹如一大堆抽屉。 需要存储多个元素时，可使用数组或链表。 数组的元素都在一起。 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。 数组的读取速度很快。 链表的插入和删除速度很快。 在同一个数组中，所有元素的类型都必须相同（都为int、double等）。

  • 递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。我很喜欢Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

  • 编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

  • 调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。

  • 这个栈用于存储多个函数的变量，被称为调用栈。

  • 使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。

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

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

  • 如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？使用D&C策略！D&C算法是递归的。使用D&C解决问题的过程包括两个步骤。 (1) 找出基线条件，这种条件必须尽可能简单。 (2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

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

  • 归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。归纳条件是这样的：如果我站在一个横档上，就能将脚放到上面一个横档上。换言之，如果我站在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。

  • 快速排序的独特之处在于，其速度取决于选择的基准值。

  • 还有一种名为合并排序（merge sort）的排序算法，其运行时间为O(n log n)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。 与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。你可能会有如下疑问。   这里说的最糟情况和平均情况是什么意思呢？ 若快速排序在平均情况下的运行时间为O(n log n)，而合并排序的运行时间总是O(n log n)，为何不使用合并排序？它不是更快吗？

  • 正如你看到的，二分查找的速度还是快得多，常量根本没有什么影响。 但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。

  • 完成每层所需的时间都为O(n)。 在这个示例中，层数为O(log n)（用技术术语说，调用栈的高度为O(log n)），而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。 在最糟情况下，有O(n)层，因此该算法的运行时间为O(n) * O(n) = O(n2)。 知道吗？这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一，也是D&C典范。

  • D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)快得多。

  • 散列函数必须满足一些要求。   它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

  • 数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。

  • 散列表适合用于：   模拟映射关系；

  • 缓存/记住数据，以免服务器再通过处理来生成它们。

  • 这种情况被称为冲突（collision）：给两个键分配的位置相同。这是个问题。如果你将鳄梨的价格存储到这个位置，将覆盖苹果的价格，以后再查询苹果的价格时，得到的将是鳄梨的价格！冲突很糟糕，必须要避免。处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。

  • 散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好，这些链表就不会很长！

  • 在平均情况下，散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。

  • 在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。

  • 在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：   较低的填装因子； 良好的散列函数。

  • 填装因子度量的是散列表中有多少位置是空的。

  • 一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）

  • 填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

  • 良好的散列函数让数组中的值呈均匀分布。

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

  • 第一种图算法——广度优先搜索（breadth-first search，BFS）。 广度优先搜索让你能够找出两样东西之间的最短距离

  • 这种问题被称为最短路径问题（shortest-path problem）。你经常要找出最短路径，这可能是前往朋友家的最短路径，也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。

  • 图模拟一组连接。

  • 图由节点（node）和边（edge）组成。

  • 图用于模拟不同的东西是如何相连的。

  • 广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。   第一类问题：从节点A出发，有前往节点B的路径吗？ 第二类问题：从节点A出发，前往节点B的哪条路径最短？

  • 在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。

  • 广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径。

  • 需要按添加顺序进行检查。有一个可实现这种目的的数据结构，那就是队列

  • 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车。队列的工作原理与此相同。队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。

  • 队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。

  • 有指向他们的箭头，但没有从他们出发指向其他人的箭头。这被称为有向图（directed graph），其中的关系是单向的。

  • 无向图（undirected graph）没有箭头，直接相连的节点互为邻居。

  • 广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V 为顶点（vertice）数，E 为边数。 练习 下面的小图说明了我早晨起床后要做的事情。

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

  • 这是最短路径，因为段数最少——只有三段，但不一定是最快路径。如果给这些路段加上时间，你将发现有更快的路径。

  • 前一章使用了广度优先搜索，它找出的是段数最少的路径（如第一个图所示）。如果你要找出最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉算法（Dijkstra’s algorithm）。

  • 广度优先搜索来查找两点之间的最短路径，那时“最短路径”的意思是段数最少。在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。

  • 狄克斯特拉算法包含4个步骤。 (1) 找出最便宜的节点，即可在最短时间内前往的节点。 (2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。 (3) 重复这个过程，直到对图中的每个节点都这样做了。 (4) 计算最终路径。（下一节再介绍！）

  • 狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。

  • 带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。

  • 要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。

  • 在无向图中，每条边都是一个环。狄克斯特拉算法只适用于有向无环图（directed acyclic graph，DAG）。

  • 如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。

  • 不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Ford algorithm）。

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

  • 贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。

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

  • 动态规划算法的工作原理。动态规划先解决子问题，再逐步解决大问题。 对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

  • 使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。 但使用贪婪算法可轻松地处理这种情况！首先，尽可能多地拿价值最高的商品；如果拿光了，再尽可能多地拿价值次高的商品，以此类推。

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

  • 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。

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

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