讲座 1：导论
本课程的目标是教会你如何解决计算问题，并说明你的解决方案是正确且高效的。
问题
- 问题输入与正确输出之间的二元关系
- 通常不会为所有输入指定每一个正确输出（太多了！）
- 提供一个可验证的谓词（属性），正确输出必须满足它
- 6.006 研究的是大规模、通用输入空间上的问题
- 非通用：小输入实例
- 通用：任意大的输入
- 例子：给定任意 n 位学生，是否存在一对同生日的学生？
- 若生日只在 365 天中选，对于 n > 365，根据鸽巢原理，答案一定为真
- 假设生日的精度超过 n（包含年份、时间等）
算法
- 一个过程：将每个输入映射到一个输出（确定性）
- 若算法对每个问题输入都返回正确输出，则称其解决了该问题
- 例子：一个解决同生日问题的算法
- 保持一个姓名和生日的记录（初始为空）
- 按某个顺序询问每个学生
∗ 若生日已在记录中，返回这对学生！
∗ 否则，将姓名和生日加入记录
- 若全部学生都询问完仍无结果，则返回 None
正确性
- 程序/算法是有限大小，如何证明其正确？
- 对于小输入，可使用情况分析
- 对于任意大的输入，算法必须以某种方式使用递归或循环
- 必须使用数学归纳法（递归在计算机科学中的关键原因）
- 例子：生日匹配算法的正确性证明
- 对 k 归纳：记录中已有的学生数量
- 假设：若前 k 位中有匹配，算法在询问第 k+1 位前就返回
- 基础情况：k = 0，前 k 位无匹配
- 假设归纳假设对 k = k₀ 成立，考虑 k = k₀ + 1
- 若前 k₀ 位已有匹配，算法已返回（由归纳）
- 否则，若前 k₀ + 1 位有匹配，匹配一定包含第 k₀ + 1 位
- 那么算法直接检查第 k₀ + 1 位学生的生日是否已在记录中
效率
- 算法生成正确输出的速度有多快？
- 可用时间测量，但希望性能不依赖于机器
- 想法！统计算法返回前执行的固定时间操作数
- 通常依赖输入大小：输入越大，时间越长
- 输入大小通常称为 n，但不总是！
- 若算法以多项式时间返回，则称其为高效
- 有时某些问题不存在高效算法！（参见第 20 讲）
- 渐进符号（Asymptotic Notation）：忽略常数因子与低阶项
- 上界 (O)、下界 (Ω)、紧界 (Θ)
- 时间估计基于：1GHz 单核机器，每周期执行一次操作
- 宇宙中的粒子数估计 < 10¹⁰⁰
| 输入规模 |
常数 |
对数 |
线性 |
对数线性 |
二次 |
多项式 |
指数 |
| n |
Θ(1) |
Θ(log n) |
Θ(n) |
Θ(n log n) |
Θ(n²) |
Θ(n^c) |
2^Θ(n^c) |
| 1000 |
1 |
≈ 10 |
1000 |
≈ 10,000 |
1,000,000 |
1000^c |
2^1000 ≈ 10^301 |
| Time |
1 ns |
10 ns |
1 µs |
10 µs |
1 ms |
10^(3c−9) s |
10^281 millenia |
计算模型
- 指定机器能以 O(1) 时间执行哪些操作
- 本课程使用的模型称为 Word-RAM
- 机器字：w 位的块（w 为字长）
- 内存：可寻址的机器字序列
- 处理器支持对 O(1) 数量的机器字执行许多 O(1) 时间操作：
- 整数运算：(+、-、*、//、%)
- 逻辑操作符：(&&, ||, !, ==, <, >, <=, >=)
- 位运算：(&, |, <<, >>, ...)
- 给定地址 a：可读取、写入地址 a 的机器字
- 内存地址必须能访问内存中所有位置
- 要求：w ≥ 表示最大地址所需的位数，即 log₂n
- 32 位字 → 最多约 4GB 内存
- 64 位字 → 最多约 16EB 内存
- Python 是一个更复杂的计算模型，基于 Word-RAM 实现
数据结构
- 数据结构是一种用于存储非常量数据，并支持一组操作的方法
- 一组操作称为接口
- Sequence（序列）：外在顺序（第一个、最后一个、第 n 个）
- Set（集合）：内在属性排序（基于键的查询）
- 同一接口可能由不同数据结构实现，性能也不同
- 例子：静态数组（Static Array）
- 固定宽度槽位，固定长度，静态序列接口
StaticArray(n)：分配大小为 n 的静态数组并初始化为 0，耗时 Θ(n)StaticArray.get_at(i)：返回索引 i 处的值，耗时 Θ(1)StaticArray.set_at(i, x)：将 x 写入索引 i，耗时 Θ(1)- 存储的机器字也可存放更大对象的地址
- 类似 Python 的 tuple 加上 set_at(i, x)
- Python list 是动态数组（详见第 2 讲）
示例代码：生日匹配
def birthday_match(students):
'''
找到一对同生日的学生
输入：由 (name, bday) 元组构成的元组
输出：学生姓名组成的元组或 None
'''
n = len(students) # O(1)
record = StaticArray(n) # O(n)
for k in range(n): # n
(name1, bday1) = students[k] # O(1)
# 若生日已在记录中，返回这对学生
for i in range(k): # k
(name2, bday2) = record.get_at(i) # O(1)
if bday1 == bday2: # O(1)
return (name1, name2) # O(1)
record.set_at(k, (name1, bday1)) # O(1)
return None # O(1)
示例：运行时间分析
- 两层循环：外层 k ∈ {0, ..., n−1}，内层 i ∈ {0, ..., k}
- 运行时间为：O(n) + ∑ₖ₌₀ⁿ⁻¹ (O(1) + k·O(1)) = O(n²)
- n 的二次方是多项式时间，算高效吗？
如何解决算法问题
1. 转化为你已知的问题（使用数据结构或算法）
| 搜索问题（数据结构） |
排序算法 |
最短路径算法 |
| Static Array (L01) |
Insertion Sort (L03) |
BFS (L09) |
| Linked List (L02) |
Selection Sort (L03) |
DAG Relax (L11) |
| Dynamic Array (L02) |
Merge Sort (L03) |
DFS (L10) |
| Sorted Array (L03) |
Counting Sort (L05) |
Topo Sort (L10) |
| Direct-Access Array (L04) |
Radix Sort (L05) |
Bellman-Ford (L12) |
| Hash Table (L04) |
AVL Sort (L07) |
Dijkstra (L13) |
| Balanced BST (L06-L07) |
Heap Sort (L08) |
Johnson (L14) |
| Binary Heap (L08) |
|
Floyd-Warshall (L18) |
2. 自行设计（递归）算法
- 暴力破解
- 减而治之
- 分治
- 动态规划（第 15–19 讲）
- 贪心 / 增量法