算法图解 Notes

第一章

1.2 二分查找

1.2.2 运行时间

如果最多猜测的次数与列表长度相同,这被称为线性时间(linear time).

1.3 大O表示法

大O表示法指出了算法有多快.

使用大O表示法, 这个运行时间为O(n).

大O表示法指的并非以秒为单位的速度, 大O表示法让你能够比较操作数,它指出了算法运行时间的增速.

O(n), 这里的n为操作数, 之所以称为大O表示法, 是因为操作数前有个大O.

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

简单查找的运行时间为O(n), 二分查找的运行时间为$\logn$.

1.3.5 旅行商

计算机科学领域非常著名的旅行商问题.

找到最短旅程的方案.

第2章 选择排序

2.2 数组和链表

O(n) 是线性时间.

O(1) 是常量时间.

数组在随机读取上更快.

链表在插入上更快.

2.2.4 在中间插入

2.2.5 删除

2.3 选择排序

一般 O($\frac{n^2}{2}$) 写为 O($n^2$), 这个$\frac{1}{2}$一般会省略. 

1
2
3
4
5
6
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
return newArr

看来pop可以弹出任意的元素.

第3章 递归

如果使用循环, 程序的性能可能更高; 如果使用递归, 程序可能更容易理解.

3.2 基线条件和递归条件

编写递归函数, 必须告诉它何时停止递归. 因此, 每个递归函数都有两部分:

  • base case, 基线条件, 指函数不再调用自己
  • recursive case, 递归条件, 指函数调用自己

3.3 栈

一个重要的编程概念–call stack, 调用栈. 其只有两个操作, push, 压入和pop, 弹出.

计算机使用一个栈来表示这些内存块.

一个重要概念: 调用另一个函数时, 当前函数暂停并处于未完成状态, 该函数的所有变量的值都还在内存中.

3.3.2 递归调用栈

栈在递归中扮演着重要角色.

第4章 快速排序

Divide and Conquer, D&C, 一种递归式问题解决方法.

D&C 的工作原理:

  1. 找出简单的基线条件
  2. 确定如何缩小问题的规模, 使其符合基线条件
    D&C 并非可用于解决问题的算法, 而是一种解决问题的思路.

编写涉及数组的递归函数时, 基线条件通常是数组为空或只包含一个元素.

在很多用循环解决的方案中, 可以考虑使用递归.

4.2 快速排序

工作原理:

  1. 从数组中选择一个元素, 这个元素被称为基准值(pivot).
  2. 找出比基准值小的元素以及比基准值大的元素. 这被称为分区(partitioning).
  3. 对这两个子数组进行快速排序.
    任何元素用作基准值都可行.

归纳证明, 一种证明算法行之有效的方式, 分为两步: 基线条件和归纳条件.

4.3 再谈大O表示法

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

4.3.1 比较合并排序和快速排序

4.3.2 平均情况和最糟情况

第5章 散列表

Hashtable, 就是哈希表.

5.1 散列函数

对于同样的输入, 散列表必须返回同样的输出.

5.2 应用案例

5.2.1 将散列表用于查找

散列表能够模拟映射关系.

5,2,2 防止重复

5.2.3 用作缓存

5.3 冲突

要明白散列表的性能, 需了解什么是冲突. Collision: 给两个键分配的位置相同.

最简单的解决方法: 如果两个键映射到了同一个位置, 就在这个位置存储一个链表.

最理想的情况是, 散列函数将键均匀地映射到散列表的不同位置.

如果散列表存储的链表很长, 散列表的速度将急剧下降.

5.4 性能

在平均情况下, 无论散列表包含多少个元素, 从中获取数据所需的时间都相同, 为O(1)–常量时间.

在最糟情况下, 散列表所有操作的运行时间都为O(n)–线性时间.

为避免冲突, 需要有:

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

5.4.1 填装因子

计算:
$\frac{element number}{position number}$

填装因子大于1意味着商品数量超过了数组的位置数, 一旦填装因子开始增大, 你就需要在散列表中添加位置, 这被称为调整长度(resizing).

一个经验规则: 一旦填装因子大于0.7, 就调整散列表的长度.

5.4.2 良好的散列函数

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

糟糕的散列函数让值扎堆, 导致大量冲突.

第6章 广度优先搜索

Breadth-first search, BFS. 用于找出两样东西之间的最短距离.