浅入深出[皱眉] ★★★★★
读完时间：2020 年 8 月 17 日
出版时间：2017 年 3 月
1.2 二分查找
需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
二分查找的运行时间为对数时间（或log时间）。
2.2 数组和链表
使用数组意味着所有待办事项在内存中都是相连的（紧靠在一起的）。
链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
需要同时读取所有元素时，链表的效率很高：你读取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率真的很低。
3.1 递归
如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。
3.2 基线条件和递归条件
每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
3.3 栈
调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。
4.1 分而治之
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。
5.1 散列函数
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
5.4 性能
在平均情况下，散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。例如，你知道的，简单查找的运行时间为线性时间。
填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
6.1 图简介
解决最短路径问题的算法被称为广度优先搜索。要确定如何从双子峰前往金门大桥，需要两个步骤。
- 使用图来建立问题模型。
- 使用广度优先搜索解决问题。
6.4 实现图
散列表是无序的，因此添加键—值对的顺序无关紧要。
6.5 实现算法
如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。
7.2 术语
要计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使用狄克斯特拉算法。
8.2 背包问题
在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
9.2 背包问题FAQ
每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低！
9.3 最长公共子串
在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
11.1 树
在二叉查找树中查找节点时，平均运行时间为O(log n)，但在最糟的情况下所需时间为O(n)；而在有序数组中查找时，即便是在最糟情况下所需的时间也只有O(log n)，因此你可能认为有序数组比二叉查找树更佳。然而，二叉查找树的插入和删除操作的速度要快得多。
如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆，伸展树。
11.5 MapReduce
分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。
11.6 布隆过滤器和HyperLogLog
布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。为判断网页以前是否已搜集，可不使用散列表，而使用布隆过滤器。使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。
11.8 局部敏感的散列算法
希望散列函数是局部敏感的。在这种情况下，可使用Simhash。如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。
