巴尔加瓦 - 计算机榜-编程设计
本书示例丰富，图文并茂，以简明易懂的方式阐释了算法，旨在帮助程序员在日常项目中更好地利用算法为软件开发助力。前三章介绍算法基础，包括二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法，具体内容包括：面对具体问题时的解决技巧，比如何时采用贪婪算法或动态规划；散列表的应用；图算法；K最近邻算法。本书适合所有程序员、计算机专业相关师生以及对算法感兴趣的读者。
我是视觉型学习者，对图解式写作风格钟爱有加。 c:176
遇到问题时，如果不确定该如何高效地解决，可尝试分而治之（第4章）或动态规划（第9章）；如果认识到根本就没有高效的解决方案，可转而使用贪婪算法（第8章）来得到近似答案。 c:472
强烈建议你动手执行示例代码，这部分的重要性再怎么强调都不过分。可以原封不动地输入代码，也可从www.manning.com/books/grokking-algorithms或https://github.com/egonschiele/grokking_algorithms下载，再执行它们。这样，你记住的内容将多得多。 c:666
需要重温算法的计算机专业毕业生 c:31
本书的示例代码可从出版社网站www.manning.com/books/grokking-algorithms下载，也可从https://github.com/egonschiele/grokking_algorithms下载。 c:339
算法是一组完成任务的指令。任何代码片段都可视为算法 c:783
该使用合并排序算法还是快速排序算法，或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。 c:285
你将学习使用K最近邻算法编写推荐系统； c:130
如果你不懂任何编程语言但想学习一门，请选择Python，它非常适合初学者； c:87
二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。 c:1263
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！ c:149
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。 c:1262
大O表示法是一种特殊的表示法，指出了算法的速度有多快。 c:652
算法的运行时间以不同的速度增加 c:130
简单查找算法编写起来更容易，因此出现bug的可能性更小 c:140
有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。 c:878
大O表示法计算的是操作数 c:251
算法的速度指的并非时间，而是操作数的增速。 c:1277
算法运行时间并不以秒为单位。❑ 算法运行时间是从其增速的角度度量的。❑ 算法运行时间用大O表示法表示。 c:704
学习两种最基本的数据结构——数组和链表，它们无处不在。 c:204
必须知道大O表示法和对数 c:30
计算机就像是很多抽屉的集合体，每个抽屉都有地址。 c:144
需要存储多项数据时，有两种基本方式——数组和链表。 c:347
需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。 c:1072
有两种访问方式：随机访问和顺序访问。 c:693
熟悉数组、链表和大O表示法 c:47
一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。 c:79
选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O(n log n) c:355
在同一个数组中，所有元素的类型都必须相同（都为int、double等）。 c:431
学习如何将问题分成基线条件和递归条件。 c:373
请用纸和笔逐步执行至少一个递归函数，就像这样：我使用5来调用factorial，这将使用4调用factorial，并将返回结果乘以5，以此类推。这样逐步执行递归函数可搞明白递归函数的工作原理。 c:49
伪代码是对手头问题的简要描述，看着像代码，但其实更接近自然语言。 c:218
如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。 c:1371
由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。 c:316
每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。 c:2179
调用栈（call stack） c:181
计算机在内部使用被称为调用栈的栈。 c:121
调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。 c:839
每个fact调用都有自己的x变量。在一个函数调用中不能访问另一个的x变量。 c:238
3.4 小结❑ 递归指的是调用自己的函数。❑ 每个递归函数都有两个条件：基线条件和递归条件。❑ 栈有两种操作：压入和弹出。❑ 所有函数调用都进入调用栈。❑ 调用栈可能很长，这将占用大量的内存。 c:754
分而治之（divide and conquer, D&C）——一种著名的递归式问题解决方法。 c:853
你要将这块地均匀地分成方块，且分出的方块要尽可能大。 c:51
(1) 找出基线条件，这种条件必须尽可能简单。 (2) 不断将问题分解（或者说缩小规模），直到符合基线条件。 c:825
余下的这块土地满足基线条件，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！ c:66
这里重申一下D&C的工作原理： (1) 找出简单的基线条件； (2) 确定如何缩小问题的规模，使其符合基线条件。 c:508
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。 c:792
。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了 c:182
数组中选择一个元素，这个元素被称为基准值（pivot）。 c:317
- 选择基准值。 (2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。 (3) 对这两个子数组进行快速排序。 c:244
你知道如何对包含三个元素的数组进行排序：对其递归地调用快速排序。 c:38
不管如何选择基准值，你都可对划分得到的两个子数组递归地进行快速排序。 c:22
归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。 c:294
下面是快速排序的代码。 c:48
快速排序的独特之处在于，其速度取决于选择的基准值。 c:553
快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。 c:390
但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多。 c:445
大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。 c:428
学习散列表的内部机制：实现、冲突和散列函数 c:167
散列函数“将输入映射到数字”。 c:498
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。 c:556
散列表由键和值组成。在前面的散列表book中，键为商品名，值为商品价格。散列表将键映射到值。 c:172
Python提供了一种创建散列表的快捷方式——使用一对大括号。 c:86
这个过程被称为DNS解析（DNS resolution），散列表是提供这种功能的方式之一。 c:425
如果“tom”在散列表中，函数get将返回它；否则返回None。你可使用这个函数检查来投票的人是否投过票！ c:74
如果你将已投票者的姓名存储在列表中，这个函数的速度终将变得非常慢，因为它必须使用简单查找搜索整个列表。但这里将它们存储在了散列表中，而散列表让你能够迅速知道来投票的人是否投过票。使用散列表来检查是否重复，速度非常快。 c:183
这里总结一下，散列表适合用于：❑ 模拟映射关系；❑ 防止重复；❑ 缓存/记住数据，以免服务器再通过处理来生成它们。 c:535
这里总结一下，散列表适合用于： ❑ 模拟映射关系； ❑ 防止重复； ❑ 缓存/记住数据，以免服务器再通过处理来生成它们。 c:405
要明白散列表的性能，你得先搞清楚什么是冲突。 c:33
首先，我撒了一个善意的谎。我之前告诉你的是，散列函数总是将不同的键映射到数组的不同位置。 c:70
处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。 c:645
而要避免冲突，需要有：❑ 较低的填装因子；❑ 良好的散列函数。 c:674
一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。 c:1013
❑ 你可以结合散列函数和数组来创建散列表。 ❑ 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。 ❑ 散列表的查找、插入和删除速度都非常快。 ❑ 散列表适合用于模拟映射关系。 ❑ 一旦填装因子超过0.7，就该调整散列表的长度。 ❑ 散列表可用于缓存数据（例如，在Web服务器上）。 ❑ 散列表非常适合用于防止重复。 c:434
广度优先搜索让你能够找出两样东西之间的最短距离 c:508
解决最短路径问题的算法被称为广度优先搜索。 c:883
图用于模拟不同的东西是如何相连的。 c:121
广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。 ❑ 第一类问题：从节点A出发，有前往节点B的路径吗？ ❑ 第二类问题：从节点A出发，前往节点B的哪条路径最短？ c:529
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。 c:313
队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。 c:418
队列是一种先进先出（First In First Out, FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。 c:688
散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。 c:366
先概述一下这种算法的工作原理。 c:37
这个函数检查人的姓名是否以m结尾 c:22
检查完一个人后，应将其标记为已检查，且不再检查他 c:236
检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个列表来记录检查过的人。 c:347
广度优先搜索的运行时间为O(人数+边数)，这通常写作O(V+E)，其中V为顶点（vertice）数，E为边数。 c:615
如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。 c:578
树是一种特殊的图，其中没有往后指的边。 c:316
你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。❑ 对于检查过的人，务必不要再去检查，否则可能导致无限循环。 c:344
介绍狄克斯特拉算法，让你能够找出加权图中前往X的最短路径。 c:176
狄克斯特拉算法包含4个步骤。 (1) 找出“最便宜”的节点，即可在最短时间内到达的节点。 (2) 更新该节点的邻居的开销，其含义将稍后介绍。 (3) 重复这个过程，直到对图中的每个节点都这样做了。 (4) 计算最终路径。 c:547
对于节点B的邻居，如果找到前往它的更短路径，就更新其开销。 c:101
你对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。 c:47
如果使用广度优先搜索，找到的最短路径将不是这条，因为这条路径包含3段，而有一条从起点到终点的路径只有两段。 c:17
狄克斯特拉算法包含4个步骤。(1) 找出最便宜的节点，即可在最短时间内前往的节点。(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。(3) 重复这个过程，直到对图中的每个节点都这样做了。(4) 计算最终路径。 c:417
要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。 c:809
狄克斯特拉算法只适用于有向无环图（directed acyclic graph, DAG）。 c:990
为计算最终路径，还需在这个表中添加表示父节点的列。 c:76
这就是狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径！ c:530
你更新了架子鼓和吉他的开销！这意味着经“黑胶唱片”前往“架子鼓”和“吉他”的开销更低，因此你将这些乐器的父节点改为黑胶唱片。 c:18
下一个最便宜的是吉他，因此更新其邻居的开销 c:23
通过沿父节点回溯，便得到了完整的交换路径。 c:125
最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。 c:241
从黑胶唱片到海报的边的权重为负！ c:21
第二种方式更划算——Rama可赚2美元！ c:13
如果有负权边，就不能使用狄克斯特拉算法。 c:684
根据狄克斯特拉算法，没有比不支付任何费用获得海报更便宜的方式。（你知道这并不对！） c:73
海报节点已处理过，这里却更新了它的开销。这是一个危险信号。节点一旦被处理，就意味着没有前往该节点的更便宜途径，但你刚才却找到了前往海报节点的更便宜途径！ c:148
在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼-福德算法（Bellman-Ford algorithm）。 c:877
因此graph["start"]是一个散列表。要获取起点的所有邻居，可像下面这样做。 c:15
节点的开销指的是从起点出发前往该节点需要多长时间 c:155
 这就是实现狄克斯特拉算法的Python代码！ c:36
开销指的是从起点前往该节点需要多长时间。 c:51
❑ 广度优先搜索用于在非加权图中查找最短路径。❑ 狄克斯特拉算法用于在加权图中查找最短路径。❑ 仅当权重为正时狄克斯特拉算法才管用。❑ 如果图中包含负权边，请使用贝尔曼-福德算法。 c:640
学习如何处理不可能完成的任务：没有快速算法的问题（NP完全问题）。 c:97
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。 (2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。 c:161
用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。 c:779
在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。 c:467
列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2n个。 c:174
这是一种近似算法（approximation algorithm）。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：❑ 速度有多快；❑ 得到的近似解与最优解的接近程度。 c:474
集合类似于列表，只是同样的元素只能出现一次，即集合不能包含重复的元素。 c:162
states_covered是一个集合，包含该广播台覆盖的所有未覆盖的州 c:28
❑ 集合类似于列表，只是不能包含重复的元素；❑ 你可执行一些有趣的集合运算，如并集、交集和差集。 c:144
因此涉及3个城市时，可能的路线有6条。 c:12
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。 c:428
NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。 c:265
他列了一个清单，指出了对球队的要求：优秀的四分卫，优秀的跑卫，擅长雨中作战，以及能承受压力等。 c:11
❑ 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。 ❑ 涉及“所有组合”的问题通常是NP完全问题。 ❑ 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。 ❑ 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。 ❑ 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。 ❑ 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。 c:591
❑ 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。 ❑ 对于NP完全问题，还没有找到快速解决方案。 ❑ 面临NP完全问题时，最佳的做法是使用近似算法。 ❑ 贪婪算法易于实现、运行速度快，是不错的近似算法。 c:535
这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题 c:260
最简单的算法如下：尝试各种可能的商品组合，并找出价值最高的组合。 c:30
动态规划先解决子问题，再逐步解决大问题。 c:325
每个动态规划算法都从一个网格开始 c:155
动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。 c:175
在每一行，可偷的商品都为当前行的商品以及之前各行的商品。 c:104
在1磅的容量中，可装入的商品的最大价值是多少呢？你之前计算过。 c:22
余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品 c:176
每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低！ c:149
使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。 c:416
这也是一个背包问题！但约束条件不是背包的容量，而是有限的时间；不是决定该装入哪些商品，而是决定该去游览哪些名胜。 c:67
但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。 c:884
在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。 c:518
❑ 单元格中的值是什么？❑ 如何将这个问题划分为子问题？❑ 网格的坐标轴是什么？ c:201
费曼算法（Feynman algorithm）。这个算法是以著名物理学家理查德·费曼命名的，其步骤如下。(1) 将问题写下来。(2) 好好思考。(3) 将答案写下来。 c:517
但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。 c:216
最长公共子序列 c:15
这里比较的是最长公共子串，但其实应比较最长公共子序列：两个单词中都有的序列包含的字母数。 c:185
你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。 c:170
❑ 需要在给定约束条件下优化某种指标时，动态规划很有用。 ❑ 问题可分解为离散子问题时，可使用动态规划来解决。 ❑ 每种动态规划解决方案都涉及网格。 ❑ 单元格中的值通常就是你要优化的值。 ❑ 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。 ❑ 没有放之四海皆准的计算动态规划解决方案的公式。 c:455
K最近邻（k-nearest neighbours, KNN）算法进行了分类 c:232
要计算两点的距离，可使用毕达哥拉斯公式。 c:139
下面是一种将用户转换为一组数字的方式。用户注册时，要求他们指出对各种电影的喜欢程度。这样，对于每位用户，都将获得一组数字！ c:62
在数学家看来，这里计算的是五维（而不是二维）空间中的距离，但计算公式不变。 c:84
你将使用KNN来做两项基本工作——分类和回归：❑ 分类就是编组；❑ 回归就是预测结果（如一个数字）。 c:384
余弦相似度（cosine similarity）。 c:232
使用KNN时，挑选合适的特征进行比较至关重要。所谓合适的特征，就是： ❑ 与要推荐的电影紧密相关的特征； ❑ 不偏不倚的特征（例如，如果只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）。 c:207
KNN算法真的是很有用，堪称你进入神奇的机器学习领域的领路人！ c:131
OCR指的是光学字符识别（optical character recognition），这意味着你可拍摄印刷页面的照片，计算机将自动识别出其中的文字。 c:347
垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（Naive Bayes classifier），你首先需要使用一些数据对这个分类器进行训练。 c:407
❑ KNN用于分类和回归，需要考虑最近的邻居。❑ 分类就是编组。❑ 回归就是预测结果（如数字）。❑ 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。❑ 能否挑选合适的特征事关KNN算法的成败。 c:417
有人设计了一种名为二叉查找树（binary search tree）的数据结构。 c:246
对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。 c:177
如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆，伸展树。 c:401
一个散列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（inverted index），常用于创建搜索引擎。 c:411
Better Explained是一个杰出的网站，致力于以通俗易懂的语言阐释数学，它就傅里叶变换做了一个绝佳的比喻：给它一杯冰沙，它能告诉你其中包含哪些成分。 c:395
负载均衡。 c:196
分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。 c:674
11.6 布隆过滤器和HyperLogLog c:68
布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。 c:354
另一种散列函数是安全散列算法（secure hash algorithm, SHA）函数。给定一个字符串，SHA返回其散列值。 c:213
你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。 c:93
当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。 c:241
希望散列函数是局部敏感的。在这种情况下，可使用Simhash。如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比较散列值来判断两个字符串的相似程度，这很有用！ c:450
这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息进行加密，以便只有收件人才能看懂呢？ c:190
Diffie-Hellman使用两个密钥：公钥和私钥。 c:146
线性规划用于在给定约束条件下最大限度地改善指定的指标。 c:401
线性规划使用Simplex算法 c:409
最佳的学习方式是找到感兴趣的主题，然后一头扎进去 c:123
栈将不断地增大。每个程序可使用的调用栈空间都有限，程序用完这些空间（终将如此）后，将因栈溢出而终止。 c:29