Ch14 §00 基础 · 讲解稿¶
章节定位: Ch14 数学地基。覆盖时间/空间复杂度 / 递归 / 分治 / 动态规划 / 主定理。 承接: Ch13 §01 离散数学 → Ch14 §00 数据结构复杂度 走向: §01 数组哈希 / §02 链表 / §03 树 / §04 图 / §05 排序 篇幅: ~4200 字 / 阅读 12 分钟 / 讲解 25-30 分钟
一 · 一句话总览¶
算法基础 = 复杂度分析 (大 O) + 递归 (函数调用栈) + 分治 (合并子问题) + DP (记忆化)。Ch14 §00 是后续 5 节的"度量衡"。
二 · 心智模型¶
把算法想成"任务": - 时间复杂度: 任务耗时 - 空间复杂度: 任务占用资源 - 递归: 任务嵌套子任务 - 分治: 任务拆 + 合并 - DP: 任务有重叠
三 · 章节主线 (5 段)¶
第 1 段 · 时间与空间复杂度 (10 分钟)¶
3.1.1 大 O 记号¶
\[T(n) = O(f(n)) \iff \exists c > 0, n_0: T(n) \leq c f(n), \forall n \geq n_0\]
含义: \(T(n)\) 增长不超过 \(c \cdot f(n)\)。
| 记号 | 含义 |
|---|---|
| \(O(f)\) | 上界 |
| \(\Omega(f)\) | 下界 |
| \(\Theta(f)\) | 紧界 |
3.1.2 分析方法¶
- 找主项: \(3n^2 + 2n + 1\) → 主项 \(3n^2\)
- 丢常数: \(3n^2 \to n^2\)
- 丢低阶: \(n^2 + n \to n^2\)
import time
n = 1_000_000
# O(n)
t0 = time.perf_counter()
s = sum(range(n))
print(f"O(n): {time.perf_counter() - t0:.4f}s")
# O(n^2)
t0 = time.perf_counter()
s = 0
for i in range(n):
for j in range(100): # 100 足够看差距
s += i * j
print(f"O(n²): {time.perf_counter() - t0:.4f}s")
3.1.3 空间复杂度¶
类似分析, 但量的是辅助空间 (不计输入)。
# O(1) 空间
def sum_n(n):
s = 0
for i in range(n):
s += i
return s
# O(n) 空间
def make_list(n):
return [i for i in range(n)]
# O(log n) 空间 (递归)
def sum_log(n):
if n == 0: return 0
return n + sum_log(n - 1) # 实际是 O(n) 因为栈深
3.1.4 平摊分析¶
单次操作均摊。e.g., 动态数组扩容: 偶尔 \(O(n)\), 但均摊 \(O(1)\)。
第 2 段 · 递归 (8 分钟)¶
3.2.1 三要素¶
- 基例 (Base case): 终止条件
- 递归调用: 规模缩小
- 返回组合
3.2.2 递归栈¶
每次调用入栈, 返回出栈。深度 = 调用次数。
3.2.3 递归 vs 迭代¶
| 维度 | 递归 | 迭代 |
|---|---|---|
| 代码 | 简洁 | 冗长 |
| 栈 | \(O(n)\) | \(O(1)\) |
| 适用 | 树 / 递归定义 | 简单循环 |
3.2.4 尾递归¶
# 尾递归 (Python 不优化)
def factorial_tail(n, acc=1):
if n == 0: return acc
return factorial_tail(n - 1, acc * n)
Python 默认不优化尾递归, 用 sys.setrecursionlimit 调高上限。
3.2.5 递归可视化: Fibonacci¶
\[F(n) = F(n-1) + F(n-2), \quad F(0) = 0, F(1) = 1\]
朴素 \(O(2^n)\), 加记忆化 \(O(n)\)。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2: return n
return fib(n - 1) + fib(n - 2)
第 3 段 · 分治 (10 分钟)¶
3.3.1 三步¶
- 分: 把问题拆成规模更小的子问题
- 治: 递归解决子问题
- 合: 合并子问题答案
3.3.2 主定理¶
\[T(n) = a T(n/b) + f(n)\]
| 条件 | 结果 |
|---|---|
| \(f(n) = O(n^{\log_b a - \epsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) |
| \(f(n) = \Theta(n^{\log_b a})\) | \(T(n) = \Theta(n^{\log_b a} \log n)\) |
| \(f(n) = \Omega(n^{\log_b a + \epsilon})\) | \(T(n) = \Theta(f(n))\) |
例: - 归并排序 \(T(n) = 2T(n/2) + O(n)\) → \(O(n \log n)\) - 二分查找 \(T(n) = T(n/2) + O(1)\) → \(O(\log n)\) - 快速排序 \(T(n) = 2T(n/2) + O(n)\) avg → \(O(n \log n)\)
3.3.3 经典分治¶
| 算法 | 拆 | 合 |
|---|---|---|
| 归并排序 | 拆两半 | 合并有序 |
| 快排 | pivot 分两半 | 已有序 |
| 大整数乘法 | Karatsuba | 合并部分积 |
| Strassen 矩阵乘 | 7 子矩阵 | 合并结果 |
3.3.4 大整数乘法 (Karatsuba)¶
朴素 \(O(n^2)\), Karatsuba \(O(n^{1.585})\)。
\[xy = (2^n a + b)(2^n c + d) = 2^{2n} ac + 2^n (ad + bc) + bd\]
关键: \(ad + bc = (a+b)(c+d) - ac - bd\), 用 3 次乘法代替 4 次。
第 4 段 · 动态规划 (10 分钟)¶
3.4.1 DP vs 分治¶
- 分治: 子问题独立
- DP: 子问题重叠, 用表缓存
3.4.2 DP 两要素¶
- 状态: \(dp[i]\) 表示什么
- 转移: \(dp[i] = f(dp[i-1], dp[i-2], ...)\)
3.4.3 经典 DP¶
| 问题 | 状态 | 转移 |
|---|---|---|
| Fibonacci | \(dp[n]\) | \(dp[n-1] + dp[n-2]\) |
| 0-1 背包 | \(dp[i][w]\) | \(\max(dp[i-1][w], dp[i-1][w-w_i] + v_i)\) |
| 最长公共子序列 | \(dp[i][j]\) | if a[i]==b[j]: +1 else max(dp[i-1][j], dp[i][j-1]) |
| 编辑距离 | \(dp[i][j]\) | 三种操作取 min |
| 最短路径 (Floyd) | \(dp[k][i][j]\) | 通过 k 中转 |
3.4.4 0-1 背包¶
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][W]
\(O(nW)\) 时间, \(O(nW)\) 空间 (可优化到 \(O(W)\))。
3.4.5 DP 优化: 滚动数组¶
只用上一行:
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
for w in range(W, weights[i] - 1, -1): # 逆序!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
3.4.6 DP 应用: Viterbi¶
隐马尔可夫模型 (Ch05) 的解码 = DP。\(dp[t][s]\) = 时刻 \(t\) 状态 \(s\) 的最大概率。
第 5 段 · 时空权衡与算法设计 (5 分钟)¶
3.5.1 时空权衡¶
| 算法 | 时间 | 空间 |
|---|---|---|
| 二分 | \(O(\log n)\) | \(O(1)\) |
| 哈希 | \(O(1)\) | \(O(n)\) |
| 数组 prefix | \(O(n)\) 预处理 | \(O(n)\) 空间, \(O(1)\) 查询 |
| 暴力 | \(O(n)\) | \(O(1)\) |
3.5.2 算法设计步骤¶
- 理解问题: 输入 / 输出 / 约束
- 找模式: 类似问题的方法
- 写伪代码
- 分析复杂度
- 边界条件
3.5.3 Python 内置数据结构¶
| 数据结构 | 访问 | 查找 | 插入 |
|---|---|---|---|
list |
\(O(1)\) | \(O(n)\) | \(O(n)\) |
dict |
- | \(O(1)\) | \(O(1)\) |
set |
- | \(O(1)\) | \(O(1)\) |
deque |
两端 \(O(1)\) | \(O(n)\) | \(O(1)\) |
heapq |
顶 \(O(1)\) | \(O(n)\) | \(O(\log n)\) |
OrderedDict |
- | \(O(1)\) | \(O(1)\) 保序 |
四 · 易错点 (5 条)¶
- 大 O 上界: 不要写成 \(T(n) = n\), 应写 \(T(n) = O(n)\)。
- 递归栈深: Python 默认 1000, 深递归会 RecursionError。
- 主定理: 必须先化简到 \(a T(n/b) + f(n)\) 形式。
- DP 维度: 多一维就多 10× 内存, 考虑压缩。
- 分治 vs DP: 子问题重叠才用 DP, 否则用分治。
五 · 跨章连接¶
| 章节 | 关联 |
|---|---|
| Ch13 §01 离散数学 | 复杂度理论 |
| Ch02 §04 矩阵 | Strassen 算法 |
| Ch05 §04 贝叶斯 | Viterbi DP |
| Ch07 §04 Transformer | 注意力可看作 DP |
| Ch12 §03 GNN | 邻居聚合是 DP-like |
六 · 自测 5 题¶
- 大 O 记号的精确定义?
- 主定理三种情况?
- 分治 vs DP 的区别?
- 0-1 背包的状态转移方程?
- Python dict 的时间复杂度?
七 · 一句话总结¶
算法基础 = 复杂度分析 (大 O) + 递归 (栈) + 分治 (合并) + DP (记忆化)。Ch14 §00 是后续 5 节"度量衡": 任何算法, 先看复杂度, 再看实现。
八 · 板书建议¶
[板书 1: 大 O]
T(n) = O(f(n)) 上界
Ω, Θ
[板书 2: 主定理]
T(n) = a T(n/b) + f(n)
三情况 vs n^{log_b a}
[板书 3: 递归]
基例 + 递归 + 组合
栈深 = O(n)
[板书 4: DP]
状态 + 转移
0-1 背包
九 · 参考资料¶
- Cormen et al., "Introduction to Algorithms" (CLRS)
- Kleinberg & Tardos, "Algorithm Design"
- Python
lru_cache文档 - Ch13 §01 离散数学 (本套书)
- Ch07 §04 Transformer (本套书)