同一个问题，有很多种算法
算法就是解决问题的一组精确步骤。大多数问题都不止一种算法能解决。比如在名单里找一个名字，你可以把每个名字都看一遍，也可以（如果名单已排好序）不断把名单对半砍掉。
两种方法答案都对，区别在于效率：各自需要多少工作量和内存。好的程序员会选择数据变大后依然很快的算法。
怎样比较算法用的时间
用秒表计时并不公平：电脑快，慢算法也会显得不错。所以我们数基本步骤（比较、交换、加法），把它写成输入规模n的函数。
最好、平均和最坏情况
最好情况是最走运的输入（13就在第一个盒子里：1步）。最坏情况是最倒霉的输入（13根本不在里面：n步）。我们通常说最坏情况，因为它是一个保证：算法永远不会比这更慢。
时间复杂度和空间复杂度
时间复杂度说明步数怎样随n增长。空间复杂度说明额外内存怎样随n增长。归并排序很快，但需要额外内存；冒泡排序几乎不需要额外内存，但很慢。
大O表示法
大O描述增长的速度，忽略小细节。我们只保留最大的那一项，并去掉常数：3n² + 5n + 2 写成O(n²)，因为n很大时，n²那一项几乎占了全部。
| 大O | 名称 | n = 16 | n = 1000 | 例子 |
|---|---|---|---|---|
| O(1) | 常数阶 | 1 | 1 | 读取数组的第5项 |
| O(log n) | 对数阶 | 4 | 约10 | 二分查找 |
| O(n) | 线性阶 | 16 | 1000 | 顺序查找、找最大值 |
| O(n log n) | n log n阶 | 64 | 约10,000 | 归并排序 |
| O(n²) | 平方阶 | 256 | 1,000,000 | 冒泡排序、嵌套循环 |
看代码的快速规则：一个循环走n个数据是O(n)；循环里再套一个循环是O(n²)；每次把问题砍掉一半是O(log n)。
顺序查找和二分查找的效率
顺序查找一个一个地检查。最坏情况：比较n次，所以是O(n)。无论列表有没有排序都能用。
二分查找需要已排序的列表。先看中间那个；如果它太大，就扔掉右半边，否则扔掉左半边。每一步都让列表减半，所以最坏情况大约是log₂ n + 1次比较：O(log n)。对于1,000,000个数据，大约只要20步，而不是1,000,000步。
排序算法的效率
冒泡排序、插入排序和选择排序都是循环里套循环，所以大约要n²/2次比较：O(n²)。插入排序在最好情况（列表本来就排好了）下是O(n)。
归并排序大约把列表对半分log₂ n次，每一层大约做n的工作量：O(n log n)。它需要O(n)的额外内存。
二分查找需要排好序的列表。如果只查一次，先排序（n log n）比一次顺序查找（n）花得更多。如果要查很多次，排一次序就划算了。
前置条件、后置条件和递归的陷阱
前置条件是算法开始前必须成立的事（二分查找：列表已排序）。后置条件是算法结束时保证成立的事（排序：每个数据都小于或等于后一个）。把它们写下来，有助于测试和证明算法。
递归是指函数在更小的问题上调用它自己。常见错误：
- 没有基本情况，或者基本情况永远到不了：调用永远不会停止（栈溢出）。
- 每次调用问题都没有变小。
- 重复做同样的工作：简单的递归斐波那契会一遍又一遍地调用fib(3)，所以它像O(2ⁿ)那样增长。把答案存起来（记忆化）就能变成O(n)。
- 递归太深会占用很多内存，每次调用占一个栈帧。
动手试试：让两种查找比赛
在纸条上写下1到32的数字，按顺序正面朝下摆好。让朋友选一个秘密数字。先一张一张地翻，数一数翻了几张。再换成每次都翻中间那一张。重复5次。哪种方法从来不需要翻超过6次？用最后一个3D步骤里的滑块检查一下（n = 32：log₂ 32 = 5）。
重点公式和概念
- 顺序查找：最坏情况n次比较 → O(n)
- 二分查找：最坏情况约log₂ n + 1次比较 → O(log n)
- 冒泡 / 插入 / 选择排序：约n(n − 1)/2次比较 → O(n²)
- 归并排序：约n log₂ n次比较 → O(n log n)
- 大O规则：保留最大的项，去掉常数（5n² + 3n → O(n²)）
- n加倍时：O(1)不变，O(log n) +1，O(n) ×2，O(n²) ×4
例题讲解
1. 一份名单有50个名字。顺序查找在最好和最坏情况下各需要几次比较？
最好情况：名字排第一 → 1次比较。最坏情况：名字在最后或根本不在 → 50次比较。顺序查找是O(n)。
2. 对1024个数据的已排序列表，二分查找最多需要几次比较？
每一步让列表减半：1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1。一共减半10次，再加最后一次检查：最多11次比较（log₂ 1024 = 10）。
3. 求f(n) = 4n² + 10n + 7的大O。
保留最大的项（4n²），去掉常数4：O(n²)。
4. 一个循环里i从1走到n，里面另一个循环里j从1走到n。里面那一行代码一共运行多少次？
i的每个值运行n次，共n个值：n × n = n²。时间复杂度O(n²)。
5. 一个O(n²)的程序排1000个数据用2秒。排3000个数据大约要多久？
n变成3倍，所以n²变成3² = 9倍：大约2 × 9 = 18秒。
6. 比较n = 1000个数据时的冒泡排序和归并排序。
冒泡排序：约n²/2 = 500,000次比较。归并排序：约n log₂ n = 1000 × 10 = 10,000次。归并排序的工作量少约50倍，但需要额外内存。
常见错误
- 只在一台电脑上用秒表测速度。应该数步数，看它随n怎样变化。
- 对没排序的列表用二分查找。它的前置条件是列表已排序。
- 在大O里保留常数，比如写成O(2n)。它就是O(n)。
- 写递归函数时没有基本情况，或者每次调用问题都没有变小。