⚡ 考前 3 小时速背卡

每一条都在考卷上有直接对应的题。带上这张卡进考场前反复看。记号：✓ 对 / ✗ 错 / ⚠️ 高频陷阱。

一、45 道判断题 — 30 秒速背（看题面→反射答案）

渐进记号（1～11）

#	关键词	✓/✗	口诀
1	$f (n) = O (f (n))$	✓	自反
2	$O (f) + O (g) = O (max)$	✓	和看大
3	$O (f) + O (g) = O (min)$	✗⚠️	应取 max
4	$Ω$ 传递	✓	不低于可传
5	$f = O (g) \to g = Ω (f)$	✓	对偶
6	$f = Ω (g) \to g = Ω (f)$	✗⚠️	方向反
7	$max (f, g) = Θ (f + g)$	✓	同阶
8	$2^{n + 1} = O (2^{n})$ 且 $2^{n} = O (2^{2 n})$	✓	+1 只差常数
9	$2^{n + 1} = O (2^{n})$ 且 $2^{2 n} = O (2^{n})$	✗⚠️	$4^{n} \neq O (2^{n})$
10	算法复杂度→问题复杂度上界	✓	一算法一上界
11	最坏比平均易算	✓	平均要分布

排序/最值下界（12～19）

#	关键词	✓/✗	口诀
12	合并排序用分治	✓
13	确定性快排 worst=已序	✓
14	随机化快排 worst=已序	✗⚠️	随机后与输入无关
15	随机化快排降平均复杂度	✗⚠️	仍 $O (n \log n)$
16	排序下界 $0.5 n \log n$	✓	合法下界
17	找最大+最小下界 $n / 2$	✓	合法非紧
18	找最大下界 $Ω (n / 3)$	✗⚠️	紧 $Ω (n)$
19	找最小下界 $Ω (n / 2)$	✓	合法下界

策略概念（20～28）

#	关键词	✓/✗	口诀
20	回溯深度优先	✓	DFS
21	回溯深度或广度优先	✗⚠️	仅 DFS
22	回溯深度或广度优先	✗⚠️	仅 DFS
23	DP 空间换时间	✓	存表
24	DP 阶段序列="决策"	✗⚠️	应叫"策略"
25	贪心部分解不一定可行	✗⚠️	贪心保持可行
26	贪心空间换时间	✗⚠️	DP 的特征
27	贪心可基于局部也可全局	✓
28	正确算法有限时间输出	✓	定义

概率算法（29～31）

#	关键词	✓/✗	口诀
29	LV 有时不给解但给就对	✓	LV 定义
30	LV 给解就对	✓
31	MC 有时不给解但给就对	✗⚠️	那是 LV！MC 总给解但可能错

P/NP 高危区（32～42）

#	关键词	✓/✗	口诀
32	所有问题最难=NP 完备	✗⚠️	NP内最难
33	NP 完全比所有 NP 都难	✗⚠️	彼此等难
34	NP 完备是所有 NP 中最难	✗⚠️	等难！
35	" $P \subset N P$ 表示"是错的	⚠️	$P \subseteq N P$ 已知/真包含未证
36	P/NP 不可用 $P \subset N P$	✓	按 merged
37	NP 问题一定不是 P	✗⚠️	$P \subseteq N P$ ！
38	非 NP 可能是 P	✗⚠️	非 NP→非 P
39	P 易解、NP 易验证	✓	直观定义
40	P2 转化到 P1→P2 更难	✗⚠️	P1 更难
41	"求一组赋值"是判定	✗	搜索问题
42	"求最大团尺寸"是判定	✗	优化问题

近似算法（43～45）

#	关键词	✓/✗	口诀
43	FPTAS 多项式时间(漏 $1 / ε$ )	✗⚠️	要对 $n$ 和 $1 / ε$
44	单实例比 3→性能比 3	✗⚠️	单实例只是下界
45	单实例比 2→性能比 2	✗⚠️	同上

二、12 道选择题答案串

C A D B C / B B A C A / B C（11 题答案 B= $2^{n}$ ，12 题答案 C= $n!$ ）

1	C：目标同、搜索方式不同	7	B：MC 无法判定对错
2	A：深度优先	8	A：费尔马小定理
3	D：无序树	9	C：多项式=易处理
4	B：分支限界	10	A：不高于
5	C：栈式	11	B： $2^{n}$
6	B：MC 近似解	12	C： $n!$

三、填空题 5 条答案

判定树填排序结论（按 a:b / a:c / b:c 分支）
输入、输出、确定性、有限性
时间复杂性、空间复杂性
L 骨牌 $= \frac{4^{k} - 1}{3}$ ； $T (k) = 4 T (k - 1) + O (1) = O (4^{k})$
$η = max {c / c^{*}, c^{*} / c}$ （恒 $\geq 1$ ）

四、必背答题模板（5 个）

分治大题

【分治思路】分：二分；治：递归左右；合：处理跨中点。
【伪代码】递归出口 if n≤1 → 二分子问题递归 → 合并过程。
【复杂度】T(n)=2T(n/2)+O(合并)=O(n log n)（或视合并代价而定）。
【与蛮力比较】蛮力 O(n²)，分治更优。

DP 大题（最高频）

【状态】设 f[k][s]：前 k 个对象、剩余资源 s 的最优值。
【决策】u：分配给第 k 个对象的量，0≤u≤s。
【转移】f[k][s] = max/min_{0≤u≤s} { g_k(u) + f[k+1][s-u] }
【边界】f[n+1][s] ≡ 0。
【手工填表】逆序逐表算（先 f_n → f_1），正向回溯读方案。

贪心大题

【策略】按 __ 排序，每步选取当前 __ 最小的 __。
【伪代码】排序 + for 循环依次贪心选。
【复杂度】O(n log n)。
【说明】贪心不一定最优（若要求最优改用 DP）。

回溯 SAT

【分支】按变量顺序，左 1 右 0。代入后化简 CNF：
  - 子句有真文字→删句；文字为假→划掉；子句变空→剪枝回溯。
【画搜索树】结点标注化简后 CNF。
【结论】给出可满足赋值。

分支限界（四问）

① 二叉搜索树：每对象一层，左枝=选，右枝=不选。
② 遍历：不剪就前进，先左后右分支，搜完回溯。
③ 下界 = 已付出 + 到终点最小剩余（Dijkstra 预求，正确&有效）。
   上界 = 迄今最优解。下界 ≥ 上界 则剪枝。
④ 伪代码：递归 search(已选集,弃集)，到终点更新最优。

五、必记公式

公式	含义	对应题
$T (n) = 2 T (n / 2) + O (n) = O (n \log n)$	归并排序 / 逆序对	D1
$T (n) = T (n / 2) + O (1) = O (\log n)$	二分查找	—
$T (n) = 4 T (k - 1) + O (1) = O (4^{k})$	棋盘覆盖	填空 4
$T (n) = 2 T (n / 3) + O (1) = O (\log_{3} N)$	假币（三分法）	D4
$m [l, h] = min_{l < i < h} {m [l, i] + m [i, h] + d_{l - 1} d_{i} d_{h}}$	矩阵链乘	P1
$c [i, j] = {\begin{cases} c [i - 1, j - 1] + 1 & x_{i} = y_{j} \\ max (c [i - 1, j], c [i, j - 1]) & x_{i} \neq y_{j} \end{cases}$	LCS	P2
$f_{k} (s) = max_{0 \leq u \leq s} {g_{k} (u) + f_{k + 1} (s - u)}$	资源分配 DP	P3～P6
$f (i) = max {f (i - 1), p_{i} + f (p r e v (i))}$	广告牌	P7
$P_{接受} = e^{- Δ E / T}$	模拟退火	Q18
$η = max {c / c^{}, c^{} / c}$	性能比	填空 5
$J (n) = 2 k + 1$ ， $n = 2^{m} + k$	约瑟夫斯	O1
$期望提问 = \frac{\sum 合并值}{\sum 频数}$	Huffman	R3

六、必记结论

结论	对应题
比较排序紧下界 $Ω (n \log n)$	Q11
同时找最大最小紧下界 $⌈ 3 n / 2 ⌉ - 2$ ，16 球=22 次	Q16
找第二小下界 $n + ⌈ \log_{2} n ⌉ - 2$ ，紧	Q12
矩阵链乘 $d = [3, 4, 6, 1, 5]$ → 最小开销 51	P1
LCS `abcbcc`/`cacbac` → 长度 4，`acbc`	P2A
投资 8 万分 3 项目 → 最大 140（ $4 + 4 + 0$ ）	P3
生产库存 4 月 → 最低 20.5（ $5, 0, 6, 0$ ）	P4
货车 5 台分 3 公司 → 最大 20	P5
货物 6 箱卸 4 店 → 最大 17	P6
TSP 遗传 → 最佳 `126543`，适应值 80	大题
SAT 四子句 → $p = q = r = s = 1$	B2
版本 A Huffman 频数 1～9 → 期望 3.0	R3
版本 B Huffman 频数 1～7 → 期望 ≈2.64	R3
指纹法 10 万位 → 7 次 × 35 比特 ≈ 245 比特	R2
$1.5 n^{2} + 365 n \log n = O (n^{2})$ （ $c = 366.5, n_{0} = 1$ ）	Q15

七、九对易混概念（一句话记）

A	B	区别
分治	DP	分治独立 / DP 重叠存表
贪心	DP	贪心不回头不一定最优 / DP 保最优
回溯	分支限界	回溯 DFS 求可行 / 分支限界 BFS/优先队列求最优
MC	LV	MC 总给解可能错 / LV 给必对可能不给
归约	转化	归约=当子程序 / 转化=构造实例
P	NP	P 能解 / NP 能验证
NPC	NP-hard	NPC∈NP / NP-hard 不要求∈NP
减治	分治	减治解一个子问题 / 分治解多个
队列式	优先队列式	队列=BFS 波前 / 优先队列=最小耗费

八、最毒判断陷阱 TOP 10

NP 完全"比所有 NP 都难"→✗（彼此等难）
单实例比值=性能比→✗（性能比取所有实例最坏）
$O (f) + O (g) = O (min)$ →✗（取 $max$ ）
随机化快排"降平均复杂度"→✗（仍 $O (n \log n)$ ）
回溯"也可广度优先"→✗（仅 DFS）
MC"不给解但给就对"→✗（那是 LV）
"贪心空间换时间"→✗（那是 DP）
$P_{2} \leq_{p} P_{1}$ → $P_{2}$ 更难→✗（ $P_{1}$ 更难）
"求赋值"/"求最大团尺寸"是判定→✗（搜索/优化）
FPTAS 漏 $1 / ε$ →✗（要对 $n$ 和 $1 / ε$ 都多项式）

九、考前最后三件事

背熟 DP 四步模板（状态/决策/转移方程/边界）→ 大题 15～20 分稳拿。
把判断题 45 条顺一遍（尤其 ⚠️ 标注的 10 条陷阱）→ 判断 15～30 分稳拿。
手算练一遍资源分配表（投资 P3 或货车 P5，填表过程 = 采分过程）→ DP 大题不翻车。

📌 最后印一张在脑子里：阅卷看四样——状态、决策、方程、边界，写了就有分。手算写过程不写结论，也能拿大部分过程分。

⚡ 考前 3 小时速背卡 ​

一、45 道判断题 — 30 秒速背（看题面→反射答案） ​

渐进记号（1～11） ​

排序/最值下界（12～19） ​

策略概念（20～28） ​

概率算法（29～31） ​

P/NP 高危区（32～42） ​

近似算法（43～45） ​

二、12 道选择题答案串 ​

三、填空题 5 条答案 ​

四、必背答题模板（5 个） ​

分治大题 ​

DP 大题（最高频） ​

贪心大题 ​

回溯 SAT ​

分支限界（四问） ​

五、必记公式 ​

六、必记结论 ​

七、九对易混概念（一句话记） ​

八、最毒判断陷阱 TOP 10 ​

九、考前最后三件事 ​

⚡ 考前 3 小时速背卡

一、45 道判断题 — 30 秒速背（看题面→反射答案）

渐进记号（1～11）

排序/最值下界（12～19）

策略概念（20～28）

概率算法（29～31）

P/NP 高危区（32～42）

近似算法（43～45）

二、12 道选择题答案串

三、填空题 5 条答案

四、必背答题模板（5 个）

分治大题

DP 大题（最高频）

贪心大题

回溯 SAT

分支限界（四问）

五、必记公式

六、必记结论

七、九对易混概念（一句话记）

八、最毒判断陷阱 TOP 10

九、考前最后三件事