算法设计与分析CS240期末复习指南

第一部分知识点清单按题型分类 一、计算与推演题占比约 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. 贪心策略模拟区间调度按活动结束时间非递减排序依次选取与已选集合无冲突的活动得到最大兼容子集。最小生成树MSTKruskal全局按边权升序排列依次加入当前不成环的边直到包含全部顶点。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) 是否被选取。编辑距离序列比对构建 ((m1)\times(n1)) 表。递推关系[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)计算终点 (ji\text{len}-1)枚举分割点 (k\in[i,j))递推式为[dp[i][j]\min_{k}(dp[i][k]dp[k1][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))。哈希表查找设装填因子 (\alphan/m)在链地址法下查找成功与失败的期望时间均为 (O(1\alpha))。6. 摊还分析动态表Dynamic Table连续插入 (n) 个元素表满时容量翻倍。总代价为插入代价 (n) 加上元素复制代价[124\cdots2^{\lfloor\log n\rfloor}2n,]总代价约 (3n)单次插入摊还复杂度为 (O(1))。 二、概念、判定与证明题占比约 50%此类题目常见形式为定义辨析、判断题、复杂度类归属证明或简述算法正确性思路。1. P, NP, NPC, NP-hard 定义P存在确定性多项式时间算法求解的问题。NP给定解的一个“证书”Certificate可在多项式时间内验证该解是否成立的问题。NPCNP 完全若问题 (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 Tt\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).”示例动态表中 (\Phi2\cdot\text{size}-\text{capacity})延迟队列中 (\PhiC\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}_ic_i\Delta\Phi). Substituting the values yields (\hat{c}_iO(1)k-C\cdot k). Choosing (C) sufficiently large (e.g., (C1)) 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.”模板 4NPC 证明模板适用题型证明某问题 (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/mt_{\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 → 归约自已知 NPC3-SAT / 顶点覆盖。随机快排复杂度最坏 (O(n^2))期望 (O(n\log n))。列表调度近似比(MTt\le 2\cdot\text{OPT})即 2-近似。布隆过滤器无假阴性可能有假阳性。摊还分析常用势能动态表 (\Phi2\cdot\text{size}-\text{capacity})延迟队列 (\PhiC\cdot|Q|)。