1.2 二分查找

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

1.3 大 O 表示法

  • 1.3.1 算法的运行时间以不同的速度增加
    仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大 O 表示法的用武之地。

3.1 递归

1
2
3
4
5
6
def look_for_key(box):
  for item in box:
    if item.is_a_box():
      look_for_key(item)  ←------递归！
    elif item.is_a_key():
      print "found the key!"

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

第 4 章 快速排序

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

4.3 再谈大 O 表示法

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

  • 4.3.1 比较合并排序和快速排序
    在大 O 表示法 O (n )中，n 实际上指的是这样的。
    c 是算法所需的固定时间量，被称为常量 。例如，printitems 所需的时间可能是 10 毫秒 * n ，而 printitems2 所需的时间为 1 秒 * n 。

5.1 散列函数

散列表是你学习的第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。

5.3 冲突

散列函数很重要 。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。

7.1 使用狄克斯特拉算法

狄克斯特拉算法找出的是总权重最小的路径

7.2 术语

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

7.3 换钢琴

狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径 ！

8.4 NP 完全问题

  • 8.4.2 如何识别 NP 完全问题
    NP 完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。

10.2 创建推荐系统

  • 10.2.3 挑选合适的特征
    在挑选合适的特征方面，没有放之四海皆准的法则，你必须考虑到各种需要考虑的因素。

11.1 树

二叉查找树类似于下面这样。对于其中的每个节点，左子节点的值都比它小 ，而右子节点的值都比它大 。
在二叉查找树中查找节点时，平均运行时间为 O (log n )，但在最糟的情况下所需时间为 O (n )；而在有序数组中查找时，即便是在最糟情况下所需的时间也只有 O (log n )，因此你可能认为有序数组比二叉查找树更佳。然而，二叉查找树的插入和删除操作的速度要快得多。
B 树是一种特殊的二叉树，数据库常用它来存储数据。

11.5 MapReduce

  • 11.5.1 分布式算法为何很有用
    MapReduce 是一种流行的分布式算法，你可通过流行的开源工具 Apache Hadoop 来使用它。
  • 11.5.3 归并函数
    映射是将一个数组转换为另一个数组。
    归并是将一个数组转换为一个元素。