第一部分：知识点清单（按题型分类）
🧮 一、计算与推演题（占比约 50% 以上）
此类题目通常给出具体数值、图表或序列，要求输出计算结果、推演过程或递推表格。
1. 渐近复杂度计算
- 函数阶比较：常用阶大小关系为
[
n! \gg 2^n \gg n^3 \gg n\log n \gg \log n \gg 1.
] - 递推式求解（主定理）：
对于 (T(n)=aT(n/b)+f(n))，比较 (n^{\log_b a}) 与 (f(n))（通常视 (f(n)=\Theta(n^d))）的阶：- 若 (f(n)) 阶更大，则 (T(n)=\Theta(f(n)))；
- 若 (n^{\log_b a}) 阶更大，则 (T(n)=\Theta(n^{\log_b a}))；
- 若二者阶相同，则 (T(n)=\Theta(n^{\log_b a}\log n))。
- 复杂度运算规则：
- 嵌套循环复杂度相乘（如 (O(n)\cdot O(n)=O(n^2))）；
- 顺序执行复杂度取最大值（加法规则）。
2. 贪心策略模拟
- 区间调度：按活动结束时间非递减排序，依次选取与已选集合无冲突的活动，得到最大兼容子集。
- 最小生成树（MST）：
- Kruskal：全局按边权升序排列，依次加入当前不成环的边，直到包含全部顶点。
- Prim：从指定顶点出发，每次选取连接当前树与外部顶点的最小权边，扩展树。
- 最优缓存（Farthest-in-Future）：给定访问序列，缓存满需替换时，淘汰下一次访问距离当前时间最远的元素。
3. 动态规划（DP）填表与回溯
- 0/1 背包：
构建 (n\times W) 二维表（(n) 为物品数，(W) 为容量）。
递推关系：
[
dp[i][w]=\max(dp[i-1][w],\ dp[i-1][w-w_i]+v_i)\quad (w\ge w_i),
]
否则 (dp[i][w]=dp[i-1][w])。
回溯时比较 (dp[i][w]) 与 (dp[i-1][w]) 是否相等，以判定物品 (i) 是否被选取。 - 编辑距离（序列比对）：
构建 ((m+1)\times(n+1)) 表。
递推关系：
[
dp[i][j]=\min\begin{cases}
dp[i-1][j]+1,\
dp[i][j-1]+1,\
dp[i-1][j-1]+\text{cost},
\end{cases}
]
其中 (\text{cost}=0)（字符相等）或 (1)（字符不等）。回溯箭头方向对应插入、删除或替换操作。 - 区间 DP（如矩阵链乘）：
枚举区间长度 (\text{len}) 和起点 (i)，计算终点 (j=i+\text{len}-1)，枚举分割点 (k\in[i,j))，递推式为
[
dp[i][j]=\min_{k}(dp[i][k]+dp[k+1][j]+\text{cost}(i,k,j)).
]
4. 网络流（最大流 / 最小割）
- Ford-Fulkerson 增广：在有向图中反复寻找从源点 (s) 到汇点 (t) 的增广路径（需包含残差网络中的反向边），更新路径容量，直到无增广路径。需能逐步绘制残差网络图。
- 最小割定位：最大流算法终止后，在残差网络中从 (s) 出发沿剩余容量 (>0) 的边遍历，可达顶点集合记为 (A)，不可达集合记为 (B)。割 ((A,B)) 的容量即为最大流值。
- 二分图匹配建模：构造源点 (s) 连向左部所有节点，左部节点按可行匹配连向右部节点，右部节点连向汇点 (t)。所有边容量设为 1，求最大流即得最大匹配数。
5. 随机算法期望计算
- MAX-3SAT：随机赋值时，每个子句被满足的概率为 (7/8)。若共有 (k) 个子句，则满足子句数的期望为 (7k/8)。
- 随机快速排序：比较次数的期望为 (O(n\log n))（注意最坏时间复杂度为 (O(n^2))）。
- 哈希表查找：设装填因子 (\alpha=n/m)，在链地址法下，查找成功与失败的期望时间均为 (O(1+\alpha))。
6. 摊还分析
- 动态表（Dynamic Table）：连续插入 (n) 个元素，表满时容量翻倍。总代价为插入代价 (n) 加上元素复制代价
[
1+2+4+\cdots+2^{\lfloor\log n\rfloor}<2n,
]
总代价约 (3n)，单次插入摊还复杂度为 (O(1))。
📖 二、概念、判定与证明题（占比约 50%）
此类题目常见形式为定义辨析、判断题、复杂度类归属证明，或简述算法正确性思路。
1. P, NP, NPC, NP-hard 定义
- P：存在确定性多项式时间算法求解的问题。
- NP：给定解的一个“证书”（Certificate），可在多项式时间内验证该解是否成立的问题。
- NPC（NP 完全）：若问题 (Q\in \text{NP})，且所有 NP 问题均可多项式归约至 (Q)，则 (Q) 为 NPC。
- NP-hard：若所有 NP 问题均可多项式归约至 (Q)，但 (Q) 不一定属于 NP，则 (Q) 为 NP-hard。
2. 经典多项式归约关系链
- 独立集 ⇔ 顶点覆盖：在无向图中，(S) 是独立集当且仅当 (V\setminus S) 是顶点覆盖。
- 3-SAT ≤ 独立集：每个子句构造一个三角形，不同子句间的相反文字节点间连边。
- 顶点覆盖 ≤ 集合覆盖：将图中的边视为元素，顶点视为集合（该顶点覆盖其关联的边）。
- 哈密顿回路 ≤ 旅行商问题（TSP）：构造距离矩阵，原图有边距离设为 1，无边距离设为无穷大（或足够大的数）。
3. 随机算法分类
- Las Vegas（拉斯维加斯）：结果永远正确，但运行时间是随机变量。示例：随机快速排序。
- Monte Carlo（蒙特卡洛）：运行时间有固定上界，但结果有一定概率出错。示例：MAX-3SAT 随机赋值、Karger 最小割算法。
4. 高级数据结构性质
- 斐波那契堆：Decrease-Key（减小键值）操作的摊还时间复杂度为 (O(1))，优于二叉堆的 (O(\log n))。
- 布隆过滤器（Bloom Filter）：无假阴性（False Negative），但可能有假阳性（False Positive）。即若查询某元素不存在，则结果必为不存在；若查询结果为存在，该元素不一定真实存在。
5. 近似比（Approximation Ratio）
- 定义：对于最小化问题，若算法输出值 (A) 满足 (A\le \alpha\cdot \text{OPT})（OPT 为最优值），则称算法为 (\alpha)-近似算法。
- 列表调度（List Scheduling）：该算法为 2-近似。设最大处理时间为 (t)，总处理时间为 (T)，则 (\text{OPT}\ge \max(T, t))，算法总完工时间 (M\le T+t\le 2\cdot\text{OPT})。
- 集合覆盖贪心：该贪心算法为 (\ln n)-近似（其中 (n) 为元素个数）。
第二部分：常见大题答题模板
以下模板按题型分类，每类均给出标准书写结构与关键话术，可直接套用于考场答卷。
模板 1：动态规划（DP）大题模板
适用题型：0/1 背包、编辑距离、矩阵链乘，要求写出递推式、填表、回溯找解。
【结构】
定义子问题
“Let (dp[i][j]) be the …（例如：using first (i) items with capacity (j) 的最大价值 / 将 (A[1…i]) 转换为 (B[1…j]) 的最小编辑次数）。”写出递推方程
明确边界条件与转移方程。
示例（0/1 背包）：
[
dp[0][j]=0,\quad dp[i][0]=0,
]
[
dp[i][j]=
\begin{cases}
\max(dp[i-1][j],\ dp[i-1][j-w_i]+v_i), & j\ge w_i,\
dp[i-1][j], & \text{otherwise}.
\end{cases}
]确定填表顺序
“We fill the table in increasing (i)（and increasing (j)）order, since (dp[i][]) depends only on (dp[i-1][]).”
对于区间 DP：“We fill by increasing interval length (\text{len}).”回溯构造解
“Starting from (dp[n][W]), if (dp[i][w]=dp[i-1][w]), item (i) is not selected, move to (dp[i-1][w]); otherwise, item (i) is selected, add it to the solution set, move to (dp[i-1][w-w_i]).”复杂度结尾
“Time complexity is (O(nW)) (or (O(nm))), space complexity is (O(nW)) (can be reduced to (O(W))).”
模板 2：摊还分析 – 势能法模板
适用题型：动态表扩容、带延迟删除的队列、斐波那契堆操作等。
【结构】
定义势能函数
“Define potential (\Phi(D_i)=c\cdot(\text{some measure})), where (c) is a sufficiently large constant. Ensure (\Phi(D_0)=0) and (\Phi(D_i)\ge 0) for all (i).”
示例：动态表中 (\Phi=2\cdot\text{size}-\text{capacity})；延迟队列中 (\Phi=C\cdot|Q|)。计算实际代价
“The actual cost of the operation is (O(1)+k), where (k) is the number of expensive loops/deletions performed.”计算势能变化
“The change in potential is (\Delta\Phi=\Phi(D_i)-\Phi(D_{i-1})).”
明确增加或减少的量，例如插入导致 (+\Delta)，删除导致 (-\Delta\cdot k)。得出摊还代价
“By the potential method, the amortized cost (\hat{c}_i=c_i+\Delta\Phi). Substituting the values yields (\hat{c}_i=O(1)+k-C\cdot k). Choosing (C) sufficiently large (e.g., (C>1)) makes this a constant. Hence, the amortized cost is (O(1)).”
模板 3：贪心算法正确性证明（交换论证）
适用题型：区间调度、最小延迟调度等，要求证明贪心策略最优。
【结构】
描述贪心策略
“The greedy algorithm selects the element with the earliest finish time (or smallest deadline, etc.) first.”证明贪心选择安全性（交换论证）
“Let (OPT) be an optimal solution. Let (g) be the first element chosen by the greedy algorithm. If (g\in OPT), done. Otherwise, let (a) be the first element in (OPT). Since (g) finishes no later than (a), replacing (a) with (g) does not violate feasibility and does not decrease the objective value. Thus, there exists an optimal solution containing (g).”归纳收尾
“By induction on the remaining subproblem, the same greedy choice can be applied repeatedly. Hence, the greedy algorithm produces a globally optimal solution.”
模板 4：NPC 证明模板
适用题型：证明某问题 (X) 是 NP-完全。
【结构】
证明 (X\in\text{NP})
“Given a certificate (C), we can verify its validity in polynomial time by checking … (e.g., size constraint and feasibility conditions). Hence, (X\in\text{NP}).”选择已知 NPC 问题作为归约源头
“We reduce a known NP-Complete problem (Y) (e.g., 3-SAT, Vertex Cover, Hamiltonian Cycle) to (X), denoted (Y\le_p X).”构造多项式归约
“Given an arbitrary instance of (Y), we construct an instance of (X) in polynomial time as follows: … (具体映射规则，如顶点、边、参数 (k’)). The size of the constructed instance is polynomial in the size of the original instance.”证明双向正确性
- ((\Rightarrow)) “If (Y) has a solution, then by construction (X) has a corresponding solution.”
- ((\Leftarrow)) “Conversely, if the constructed instance of (X) has a solution, then by reversing the mapping, we obtain a valid solution for (Y).”
Therefore, the two instances are equivalent.
结论
“Since (X\in\text{NP}) and (X) is NP-hard (via the reduction from (Y)), we conclude that (X) is NP-Complete.”
模板 5：近似比证明模板（以列表调度为例）
适用题型：列表调度、顶点覆盖 2-近似等。
【结构】
定义变量并下界化 OPT
“Let (T=\sum_i t_i) (total load), and (t_{\max}) be the longest job. Then (\text{OPT}\ge T/m) and (\text{OPT}\ge t_{\max}).”分析临界机器
“Consider the machine (M) that finishes last, with load (L). Let (t_j) be the last job assigned to (M). Before assigning (t_j), machine (M) had the smallest load, so (L-t_j\le T/m).”串联不等式得出近似比
“The makespan of the algorithm is (L=(L-t_j)+t_j\le T/m+t_{\max}\le \text{OPT}+\text{OPT}=2\text{OPT}). Therefore, the algorithm is a 2-approximation.”
模板 6：最大流 / 最小割建模模板
适用题型：选课冲突、篮球淘汰、图像分割等实际问题的流网络建模。
【结构】
构造网络图
“Create source (s) and sink (t). For each element (i), add edge (s\to i) with capacity (w_i) (benefit), and (i\to t) with capacity (c_i) (cost). For each conflict/constraint ((i,j)), add edge (i\to j) with capacity (\infty).”解释割的意义
“For any finite cut ((S,T)), if (i\in S) (selected) and (j\in T) (discarded), the infinite capacity edge prevents violation. The cut capacity equals (lost benefits for discarded items) + (costs for selected items).”结论与算法
“By the integrality property of max-flow, the min-cut value gives the minimum cost, and max-flow gives the maximum net profit. Run Ford-Fulkerson or Dinic to compute the result.”
第三部分：关键结论速查（考前快速浏览）
- 主定理核心：比较 (n^{\log_b a}) 与 (f(n)) 的阶，高阶决定复杂度；阶相等时结果为 (O(n^{\log_b a}\log n))。
- DP 模型识别：背包按容量建模，编辑距离按字符串长度建模，区间 DP 按区间长度递增枚举。
- NPC 证明框架：验证 NP → 归约自已知 NPC（3-SAT / 顶点覆盖）。
- 随机快排复杂度：最坏 (O(n^2))，期望 (O(n\log n))。
- 列表调度近似比：(M=T+t\le 2\cdot\text{OPT})，即 2-近似。
- 布隆过滤器：无假阴性，可能有假阳性。
- 摊还分析常用势能：动态表 (\Phi=2\cdot\text{size}-\text{capacity})；延迟队列 (\Phi=C\cdot|Q|)。
