算法设计 期末复习笔记基于 Lecture 1-7, 作业与考试热点整理考试题型: 10 选择(20分) 10 判断(10分) 4 计算 2 算法设计占位图目录算法基础与复杂度分析排序与划分算法动态规划 (DP)最短路径算法最小生成树 (MST)最大流 (Maximum Flow)二分图匹配 (Bipartite Matching)线性规划 (Linear Programming)附考试热点速查表1. 算法基础与复杂度分析1.1 渐近符号 (Asymptotic Notation)符号含义数学定义类比O(大O)上界 (最坏情况)0 ≤ f(n) ≤ c·g(n), n ≥ n₀≤Ω(大Ω)下界 (最好情况)0 ≤ c·g(n) ≤ f(n), n ≥ n₀≥Θ(大Θ)紧确界c₁·g(n) ≤ f(n) ≤ c₂·g(n), n ≥ n₀判断技巧:O 表示不会比…差最坏情况的上界Ω 表示至少和…一样好最好情况的下界Θ 表示和…同阶1.2 ⭐ Master Theorem (主定理) —唯一考查时间复杂度的方法求解递推式 T(n) aT(n/b) f(n), 其中 a ≥ 1, b 1计算log_b a, 比较 f(n) 与 n^(log_b a):Case条件结论Case 1f(n) O(n^(log_b a - ε)), ε 0T(n) Θ(n^(log_b a))Case 2f(n) Θ(n^(log_b a) · log^k n), k ≥ 0T(n) Θ(n^(log_b a) · log^(k1) n)Case 3f(n) Ω(n^(log_b a ε)), ε 0 且满足正则性条件 a·f(n/b) ≤ c·f(n), c 1T(n) Θ(f(n))要点:Case 2 最重要: f(n) 和 n^(log_b a) 同阶多一个 log 因子时也无妨Case 3 需要额外验证正则性条件(regularity condition)三个 Case 之间有空隙不是所有递推式都适用 Master Theorem经典例子:递推式ablog_b af(n)Case结果T(n) 9T(n/3) n932n O(n^(2-ε))1Θ(n²)T(n) T(2n/3) 113/201 Θ(n⁰)2Θ(log n)T(n) 3T(n/4) n34log₄3 ≈ 0.793n Ω(n^(0.793ε))3Θ(n)T(n) 2T(n/2) n221n Θ(n¹·log⁰ n)2Θ(n log n)T(n) T(n/2) n120n Ω(n^(0ε))3Θ(n)注意: T(n) T(n-1) O(n)不能用 Master Theorem因为 b 1 才适用1.3 递归树法 (Recursion Tree)当 Master Theorem 不适用时使用画出递归树的每一层计算每层的工作量对所有层求和例: T(n) T(n/3) T(2n/3) O(n)递归树深度O(log n)每层工作量O(n)总复杂度O(n log n)1.4 代入法 (Substitution Method) — 数学归纳法证明步骤猜测复杂度上界/下界归纳假设假设对小于 n 的情况成立带入递推式证明对 n 成立找到合适的常数 c, n₀1.5 ⭐ BFS / DFS 遍历算法数据结构应用BFS队列 (Queue)最短路径无权图、层次遍历DFS栈 (Stack) / 递归连通分量、拓扑排序、环路检测时间复杂度考试常考:存储方式BFS 时间BFS 空间DFS 时间DFS 空间邻接表 (Adjacency List)O(V E)O(V)O(V E)O(V)邻接矩阵 (Adjacency Matrix)O(V²)O(V²)O(V²)O(V)⭐高频考点问 BFS/DFS 在邻接表和邻接矩阵下的复杂度原因: 邻接表遍历每条边一次 → O(VE)原因: 邻接矩阵检查每个顶点对所有顶点的连接 → O(V²)2. 排序与划分算法2.1 ⭐ QuickSort 及划分算法Lomuto 划分LomutoPartition(A, p, r): pivot A[r] // 选最后一个元素为 pivot i p - 1 // i 指向小于 pivot 的最后一个元素 for j p to r-1: if A[j] ≤ pivot: i swap A[i] and A[j] swap A[i1] and A[r] // 把 pivot 放到正确位置 return i 1 // 返回 pivot 的位置特点:简单但效率略低单指针 i 跟踪 pivot 的边界Hoare 划分HoarePartition(A, p, r): pivot A[p] // 选第一个元素为 pivot i p - 1 j r 1 while True: do i while A[i] pivot do j-- while A[j] pivot if i j: swap A[i] and A[j] else: return j // 返回划分位置特点:双向扫描效率更高平均交换次数少于 Lomuto返回的索引不一定在 pivot 的位置⭐ Median-of-3 优化QuickSort(A, p, r): if p r: // Median-of-3: 选 A[p], A[(pr)/2], A[r] 的中位数作为 pivot mid (p r) / 2 if A[mid] A[p]: swap A[p], A[mid] if A[r] A[p]: swap A[p], A[r] if A[r] A[mid]: swap A[mid], A[r] swap A[mid], A[r] // 把中位数放到末尾 (配合 Lomuto) q Partition(A, p, r) QuickSort(A, p, q-1) QuickSort(A, q1, r)效果: 避免在已排序数组上出现 O(n²) 的最坏情况QuickSort 复杂度情况复杂度递推式最好O(n log n)T(n) 2T(n/2) O(n) → 均匀划分平均O(n log n)最坏O(n²)T(n) T(n-1) O(n) → 极度不平衡划分⭐高频考点何时最坏已排序数组 每次都选第一个/最后一个元素作为 pivot3. ⭐ 动态规划 (DP)核心思想最优子结构问题的最优解包含子问题的最优解重叠子问题子问题被重复求解与分治法的区别填表顺序由小到大核心三要素状态定义 → 状态转移方程 → 初始化 边界条件3.1 ⭐⭐ 0-1 背包问题 (高频压轴题)问题: n 个物品每个 i 有重量 w_i 和价值 v_i背包容量 W每个物品最多拿一个状态定义: dp[i][w] 前 i 个物品在容量为 w 时能取得的最大价值状态转移方程:dp[i][w] max(dp[i-1][w], // 不拿第 i 个物品 dp[i-1][w - w_i] v_i) // 拿第 i 个物品 (前提 w ≥ w_i)初始化: dp[0][w] 0, dp[i][0] 0时间复杂度:O(n·W)— 伪多项式时间n 为物品数W 为容量填表示例:物品: (w,v) (2,3), (3,4), (4,5), (5,6); W 8w0 w1 w2 w3 w4 w5 w6 w7 w8 i0 0 0 0 0 0 0 0 0 0 i1(2,3) 0 0 3 3 3 3 3 3 3 i2(3,4) 0 0 3 4 4 7 7 7 7 i3(4,5) 0 0 3 4 5 7 8 9 9 i4(5,6) 0 0 3 4 5 7 8 9 10回溯找到选取的物品: 从 dp[n][W] 开始如果 dp[i][w] ≠ dp[i-1][w]说明拿了 i3.2 硬币找零无限数量问题: 给定硬币面额 coins [1,3,5]无限使用凑成金额 amount求最少硬币数状态定义: dp[i] 凑成金额 i 所需的最少硬币数状态转移方程:dp[i] min(dp[i], dp[i - coin] 1) // 对每种 coin ≤ i初始化: dp[0] 0, dp[其他] ∞ (或一个大数)时间复杂度:O(n·m)(n 为金额m 为硬币种类数)填表示例: coins [1,3,5], amount 11dp[0]0 dp[1]1 dp[2]2 dp[3]1 dp[4]2 dp[5]1 dp[6]2 dp[7]3 dp[8]2 dp[9]3 dp[10]2 dp[11]3答案: dp[11] 3 (551 或 533)3.3 ⭐ LCS最长公共子序列问题: 求两个序列 X[1…m], Y[1…n] 的最长公共子序列长度状态定义: dp[i][j] X[1…i] 和 Y[1…j] 的 LCS 长度状态转移方程:dp[i][j] dp[i-1][j-1] 1, 如果 X[i] Y[j] dp[i][j] max(dp[i-1][j], dp[i][j-1]), 如果 X[i] ≠ Y[j]初始化: dp[0][j] 0, dp[i][0] 0时间复杂度:O(m·n)空间复杂度: O(m·n)可优化为 O(min(m,n))回溯:while i 0 and j 0: if X[i] Y[j]: 打印 X[i]; i--; j-- else if dp[i-1][j] dp[i][j-1]: i-- else: j--示例: X “ABCBDAB”, Y “BDCAB”LCS 长度 4LCS “BCAB” 或 “BDAB”3.4 ⭐ OBST最优二叉搜索树问题: 给定键值 K₁ K₂ … Kₙ 及其搜索概率 p₁, p₂, …, pₙ构造期望搜索代价最小的 BST核心公式:递推式1(含 dummy 键概率 q_i):e[i][j] min{e[i][r-1] e[r1][j] w[i][j]}, i ≤ r ≤ jw[i][j] w[i][r-1] p_r w[r1][j] w[i][j-1] p_j q_j递推式2考试常用简化版不加 dummy 键:cost[i][j] min{cost[i][r-1] cost[r1][j] sum(p[i…j])}, i ≤ r ≤ j其中 sum(p[i…j]) p_i p_{i1} … p_j时间复杂度:O(n³)— 三层循环区间长度 × 起点 × 根位置填表顺序: 按区间长度从小到大从 len1 到 lenn填写规则:dp[i][j]含义i jcost[i][i] p_i (单节点树, 即该节点的概率)i jcost[i][j] 0 (空树)i j在 r ∈ [i, j] 中找最小示例: n3, p[0.1, 0.2, 0.4]cost[1][1]0.1 cost[2][2]0.2 cost[3][3]0.4 cost[1][2]min( r1: cost[1][0]cost[2][2](0.10.2) 00.20.3 0.5 r2: cost[1][1]cost[3][2](0.10.2) 0.100.3 0.4 ) 0.4 (根为 K₂) ...DP 对比总结问题状态维度时间复杂度空间复杂度核心公式0-1 背包2D (n×W)O(n·W)O(n·W)max(不拿, 拿)硬币找零1DO(n·m)O(n)min(不加, 加1)LCS2D (m×n)O(m·n)O(m·n)匹配1 / maxOBST2D (n×n)O(n³)O(n²)min(左右sum)DP 考试技巧:看到最优化、“最大/最小”、“方案数” → 考虑 DP状态定义是最关键的一步转移方程确定后关注填表顺序决定能否用滚动数组优化如果要求输出具体方案 → 记住回溯的步骤4. ⭐ 最短路径算法4.1 ⭐⭐ Dijkstra 算法适用: 单源最短路径非负权重图核心思想: 贪心每次从未确定最短距离的顶点中选最近的加入 S 集Dijkstra(G, s): 初始化 dist[s] 0, dist[其他] ∞ S ∅ // 已确定最短路径的顶点集合 Q V // 优先队列最小堆按 dist 排序 while Q ≠ ∅: u Extract-Min(Q) // 从 Q 中取出 dist 最小的顶点 S S ∪ {u} for each v in Adj[u]: Relax(u, v, w) // 松弛操作 if dist[u] w(u,v) dist[v]: dist[v] dist[u] w(u,v) Decrease-Key(Q, v, dist[v]) // 更新 Q 中的优先级Relax 松弛操作:if dist[u] w(u,v) dist[v]: dist[v] dist[u] w(u,v)时间复杂度:O((V E) log V)原因: 每个顶点 Extract-Min 一次 (V × O(log V))每条边 Relax/Decrease-Key 一次 (E × O(log V))正确性条件: 适用于非负权重负权重会使贪心失效步骤示例:步骤S 集合dist 数组初始{a}a:0, b:∞, c:∞, d:∞1{a,b}a:0,b:5, c:∞, d:∞2{a,b,c}a:0, b:5,c:9, d:∞3{a,b,c,d}a:0, b:5, c:9,d:11⭐关键理解: 为什么 Dijkstra 不能处理负权重因为已加入 S 的顶点不会再被更新而负边可能使已确定的最短路径变短。4.2 ⭐ Bellman-Ford 算法适用: 单源最短路径允许负权重可检测负环Bellman-Ford(G, s): 初始化 dist[s] 0, dist[其他] ∞ // V-1 轮松弛 for i 1 to |V| - 1: for each edge (u, v) in E: Relax(u, v, w) // 检测负环 for each edge (u, v) in E: if dist[u] w(u,v) dist[v]: return FALSE // 存在负环 return TRUE时间复杂度:O(V·E)原因: V-1 轮外层循环 × E 条边的内层循环为什么是 V-1 轮最长简单路径最多 V-1 条边经过 V-1 轮松弛所有顶点的最短距离必然确定检测负环: 第 V 轮仍然能松弛 → 存在负环⭐高频考点: Bellman-Ford vs Dijkstra 的区别4.3 DAG 最短路径适用:有向无环图 (DAG)权重任意DAG-Shortest-Path(G, s): 对 G 进行拓扑排序 初始化 dist[s] 0, dist[其他] ∞ for each vertex u in topological order: for each edge (u, v) in Adj[u]: Relax(u, v, w)时间复杂度:O(V E)原因: 拓扑排序 O(VE) 每条边松弛一次 O(E)4.4 Floyd-Warshall 算法适用:所有点对最短路径DP 思想Floyd-Warshall(G): 初始化 dist[i][j] w(i,j) // 直接边权重 dist[i][i] 0 若无直接边: dist[i][j] ∞ for k 1 to V: for i 1 to V: for j 1 to V: dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])时间复杂度:O(V³)原因: 三层嵌套循环核心思想: DP 递推 — 经过前 k 个顶点中转的最短路径空间复杂度: O(V²) — 可直接在原数组上更新4.5 ⭐ Johnson 算法适用:所有点对最短路径有负边但无负环稀疏图友好核心思想: 重新赋权 (Reweighting) 将负权边转为非负然后对每个顶点跑 DijkstraJohnson(G): // 步骤1: 添加超级源点 s*到所有顶点连 0 权边 G G 加上新顶点 s* for each v in V: add edge (s*, v) with w 0 // 步骤2: 跑 Bellman-Ford 得到 h(v) dist(s*, v) if Bellman-Ford(G, s*) 检测到负环: return 存在负环 // 步骤3: 重新赋权 for each edge (u, v) in E: w(u,v) w(u,v) h(u) - h(v) // 步骤4: 对每个顶点跑 Dijkstra for each vertex u in V: Dijkstra(G, u) // 用 w 权重 // 恢复原始距离: dist(u,v) dist(u,v) - h(u) h(v)时间复杂度:O(V² log V V·E)原因分解:Bellman-Ford: O(V·E)重新赋权: O(E)V 次 Dijkstra: V × O((VE) log V) O(V² log V V·E)重新赋权为什么能保证非负?由三角不等式 h(v) ≤ h(u) w(u,v)所以 w’(u,v) w(u,v) h(u) - h(v) ≥ 0 ✓最短路径算法对比算法适用场景时间复杂度空间复杂度负边负环检测Dijkstra非负权单源O((VE)log V)O(V)❌❌Bellman-Ford任意单源O(V·E)O(V)✅✅DAG 最短路径DAG 单源O(VE)O(V)✅✅(无环)Floyd-Warshall任意全源O(V³)O(V²)✅可检测Johnson负边全源O(V²log V VE)O(V²)✅✅算法选择指南:无负边 单源 → Dijkstra有负边 单源 → Bellman-Ford有负边 全源 稀疏图 → Johnson密集图 全源 → Floyd-Warshall5. ⭐ 最小生成树 (MST)5.1 ⭐ Kruskal 算法核心思想: 贪心从小到大选边不能形成环Kruskal(G): A ∅ // MST 边集合 for each v in V: Make-Set(v) // 每个顶点初始化为一个集合 将所有边按权重从小到大排序 for each edge (u, v) in sorted edges: if Find-Set(u) ≠ Find-Set(v): // u 和 v 不在同一连通分量 A A ∪ {(u, v)} Union(u, v) // 合并两个集合 return A时间复杂度:O(E log E)原因: 排序 O(E log E) 并查集操作 O(E·α(V)) ≈ O(E)关键数据结构:并查集 (Union-Find)— Find 和 Union 近似 O(1)5.2 ⭐ Prim 算法核心思想: 从一个顶点出发贪心地选择连接树内和树外顶点的最小边Prim(G, start): for each v in V: key[v] ∞ // 到 MST 的最小距离 parent[v] NIL key[start] 0 Q V // 优先队列按 key 排序 while Q ≠ ∅: u Extract-Min(Q) for each v in Adj[u]: if v in Q and w(u,v) key[v]: parent[v] u key[v] w(u,v) Decrease-Key(Q, v, key[v])时间复杂度:O(E log V)原因: 每个顶点 Extract-Min 一次 (V × O(log V))每条边可能 Decrease-Key (E × O(log V))使用斐波那契堆可优化到 O(E V log V)Kruskal vs Prim 对比特性KruskalPrim策略选全局最小边选连接树的最小边适合稀疏图 (E ≈ V)稠密图 (E ≈ V²)时间复杂度O(E log E)O(E log V)数据结构并查集优先队列/最小堆实现难度较简单略复杂边排序需要不需要⭐注意: 两种算法等价Kruskal 全局排序选边Prim 局部贪心扩展MST 重要性质:Cut Property: 对任意割最小权重的跨越边一定在 MST 中Cycle Property: 对任意环最大权重的边一定不在 MST 中6. ⭐ 最大流 (Maximum Flow)6.1 ⭐⭐ Edmonds-Karp (EK) 算法核心思想: 用 BFS 在残量网络中找最短增广路径边数最少Edmonds-Karp(G, s, t): for each edge (u,v) in E: flow[u][v] 0 // 初始化流量为 0 while BFS 在残量网络中能找到从 s 到 t 的路径: // BFS 找到一条最短增广路径 P // 计算瓶颈容量: bottleneck min P 上的残量容量 bottleneck ∞ for each edge (u,v) in P: bottleneck min(bottleneck, c[u][v] - flow[u][v]) // 正向边 // 或 flow[v][u] // 反向边 // 更新路径上的流量 for each edge (u,v) in P: flow[u][v] bottleneck // 正向边加流量 flow[v][u] - bottleneck // 反向边减流量 return total_flow // 从 s 出发的总流量时间复杂度:O(V·E²)原因: 每次 BFS O(E)最多 O(V·E) 次增广每次增广至少增加 1 条饱和边每条边最多饱和 V/2 次BFS 找最短增广路径: 在残量网络中从 s 到 t 找边数最少的路径伪代码: 可用 parent 数组记录路径类似 BFS 找无权图最短路径6.2 核心概念概念定义残量网络 (Residual Network)G_f (V, E_f)包含正向残量边 (c - f 0) 和反向残量边 (f 0)增广路径 (Augmenting Path)残量网络中 s → t 的路径瓶颈容量 (Bottleneck)增广路径上最小的残量容量割 (Cut)(S, T) 将 V 分为两部分s ∈ S, t ∈ T割容量Σ c(u,v), u ∈ S, v ∈ T, (u,v) ∈ E6.3 ⭐⭐⭐ 最大流最小割定理定理: 在任意网络中最大流的值等于最小割的容量max ⁡ _ f l o w min ⁡ _ c u t c a p a c i t y ( S , T ) \max\_flow \min\_{cut} capacity(S, T)max_flowmin_cutcapacity(S,T)推论:流值 ≤ 任意割的容量若流值等于某个割的容量 → 该流为最大流该割为最小割⭐重难点: 理解’反向边’的作用 — 反向边提供撤销功能允许算法修正之前的不良选择考试常考: 给定网络找最大流、最小割、割容量6.4 EK 算法执行示例网络: s → a (cap10), s → b (cap5) a → b (cap15), a → t (cap5), b → t (cap10) 步骤1: BFS 找最短增广路径: s → a → t, bottleneck 5 步骤2: BFS 找最短增广路径: s → b → t, bottleneck 5 步骤3: BFS 找最短增广路径: s → a → b → t, bottleneck 5 最大流 15 最小割: S {s, a, b}, T {t}, 割容量 510 15 ✓7. ⭐ 二分图匹配 (Bipartite Matching)7.1 基本概念二分图: 顶点可划分为两个不相交集合 U 和 V所有边连接 U 和 V 中的顶点匹配 (Matching): 边的一个子集其中任意两条边没有公共顶点最大匹配: 边数最多的匹配完美匹配: 覆盖所有顶点的匹配交替路径: 已匹配边和未匹配边交替出现的路径可增广路径 (Augmenting Path): 起点和终点都是未匹配顶点的交替路径7.2 ⭐⭐ Berge’s Lemma定理: 匹配 M 是最大匹配当且仅当不存在关于 M 的增广路径7.3 ⭐⭐ 匈牙利树算法 (Hungarian Tree Algorithm)核心思想: 在二分图中用 DFS/BFS 寻找可增广路径找到则翻转路径上的边Hungarian(G, U, V, E): 初始化匹配 M ∅ for each vertex u in U: if u 未匹配: visited ∅ // 每轮重置已访问标记 if DFS(u) 找到增广路径: 翻转路径上的边状态 matching_count DFS(u): for each v in Adj[u]: // u 的邻居 if v not visited: visited[v] true if v 未匹配 或 DFS(match[v]) 成功: // 找增广路径 match[v] u return TRUE return FALSE时间复杂度:O(V·E)原因: 最多 V 次 DFS/BFS每次 O(E)DFS/BFS 搜索增广路径:从未匹配的左顶点开始走交替路径: 未匹配边 → 匹配边 → 未匹配边 → …直到找到未匹配的右顶点翻转路径上的所有边: 匹配 ↔ 未匹配匈牙利树算法执行示例U {1, 2, 3}, V {a, b, c, d} 边: 1-a, 1-b, 2-a, 2-c, 3-b, 3-d 步骤1: 从 1 出发, DFS: 1→a (a未匹配) → 匹配 1-a 匹配: M {(1,a)} 步骤2: 从 2 出发, DFS: 2→a (a已匹配1) → 1→b (b未匹配) → 翻转 匹配: M {(2,a), (1,b)} 步骤3: 从 3 出发, DFS: 3→b (b已匹配1) → 1→a (a已匹配2) → 2→c (c未匹配) → 翻转 匹配: M {(3,b), (1,a), (2,c)} 最大匹配数 37.4 二分图匹配的 ES 问题 (Exact Satisfiability)输入: 二分图 G (U ∪ V, E) 和集合族 F问题: 是否存在匹配 M 使得每个集合被精确覆盖一次解法: 构造流网络每条边容量 1用最大流求解二分图匹配与最大流的关系二分图最大匹配可以转化为最大流问题:添加超级源点 s 连左部所有顶点 (cap1)原二分图边改为从左到右的有向边 (cap1)右部所有顶点连超级汇点 t (cap1)最大匹配数 最大流值8. ⭐ 线性规划 (Linear Programming)8.1 标准形式最小化形式 → 标准形式转换规则:原始形式转换方法min → max目标函数取负约束 ≥两边取负转为 ≤约束 拆为 ≤ 和 ≥ 两个约束自由变量 xx x⁺ - x⁻, x⁺ ≥ 0, x⁻ ≥ 0变量 x ≤ 有限值x’ M - x 代入变量 x ≥ 有限值x’ x - L 代入标准形式(变量 ≥ 0):maximize: c₁x₁ c₂x₂ ... cₙxₙ subject to: a₁₁x₁ a₁₂x₂ ... a₁ₙxₙ ≤ b₁ a₂₁x₁ a₂₂x₂ ... a₂ₙxₙ ≤ b₂ ... aₘ₁x₁ aₘ₂x₂ ... aₘₙxₙ ≤ bₘ x₁, x₂, ..., xₙ ≥ 08.2 松弛形式 (Slack Form)将不等式约束转化为等式约束引入松弛变量 s₁, s₂, …, sₘ松弛变量 ≥ 0原始: a₁₁x₁ a₁₂x₂ ... a₁ₙxₙ ≤ b₁ 转换: a₁₁x₁ a₁₂x₂ ... a₁ₙxₙ s₁ b₁, s₁ ≥ 08.3 基本解 (Basic Solution)基本变量 (Basic variables, B): m 个变量构成基非基本变量 (Nonbasic variables, N): n 个变量设为 0基本解: 非基本变量 0解方程组得基本变量的值可行基本解 (Basic Feasible Solution, BFS): 所有变量 ≥ 0 的基本解8.4 ⭐⭐⭐ Simplex 算法单纯形法核心思想: 沿可行域的边移动每次迭代增加目标函数值Simplex(A, b, c): 将 LP 转换为松弛形式 找到初始 BFS (所有非基本变量 0) while True: // STF (Select Target Function): 选择目标系数为正的 NB 变量 // 选正系数最大的那个加速收敛 if 目标函数中所有 NB 变量的系数 ≤ 0: break // 达到最优解 选某个 NB 变量 x_e (系数 0) 进入基 // RLF (Ratio Limit Function): 找最紧约束 min_ratio ∞ for each 基本变量对应约束 i: if a_{i,e} 0: ratio b_i / a_{i,e} if ratio min_ratio: min_ratio ratio pivot_row i if min_ratio ∞: return 无界 // 目标函数可以无限增大 选对应的基本变量 x_l 离开基 // Pivot: 交换 x_e 和 x_l // 1. 将 x_e 用 x_l 和其他变量表示 // 2. 代入其他所有方程 // 3. 更新目标函数选择进基变量 (STF - Select Target Function):在目标函数中找到系数为正的非基本变量如果有多个正系数通常选最大的但选择策略影响收敛速度选择离基变量 (RLF - Ratio Limit Function):对每个约束计算 b_i / a_{i,e}其中 a_{i,e} 0选最小比值对应的基本变量离基这是保证新解可行的关键Pivot 操作:// 假设 xe 进基, xl 离基 // 将等式 l 写成 xe 的形式: xe bl/a_{l,e} - Σ a_{l,j}/a_{l,e} · xj - xl/a_{l,e} // 代入其他所有等式和目标函数终止条件: 目标函数中所有非基本变量系数均为负值最大值问题单纯形法示例maximize: z 3x₁ 2x₂ 约束: x₁ x₂ ≤ 4 2x₁ x₂ ≤ 6 x₁, x₂ ≥ 0步骤1: 转为松弛形式z 3x₁ 2x₂ x₁ x₂ s₁ 4 2x₁ x₂ s₂ 6 x₁, x₂, s₁, s₂ ≥ 0N {x₁, x₂}, B {s₁, s₂}步骤2: 选 x₁ 进基系数 3 0, 算比值: 4/14, 6/23 → s₂ 离基步骤3: Pivot → 新基 B {s₁, x₁}, N {x₂, s₂}x₁ 3 - 0.5x₂ - 0.5s₂ s₁ 1 - 0.5x₂ 0.5s₂ z 9 0.5x₂ - 1.5s₂步骤4: 选 x₂ 进基系数 0.5 0, 算比值: 1/0.52, 3/0.56 → s₁ 离基步骤5: Pivot → 新基 B {x₂, x₁}, N {s₁, s₂}x₂ 2 - 2s₁ s₂ x₁ 2 s₁ - s₂ z 10 - 3s₁ - 0.5s₂所有系数 ≤ 0 →最优解: x₁2, x₂2, z10 ✓单纯形法注意点退化 (Degeneracy): 某个基本变量为 0可能导致循环多个 pivot 后回到同一 BFSBland’s 规则: 选最小下标变量可避免循环初始 BFS 不可行: 需要两阶段法Phase I: 构造辅助 LP 求可行解9. 考试热点速查表⭐⭐ 极端重点 (必考)知识点考查形式关键记忆点DP (0-1背包/LCS)算法设计题(20分)状态定义 转移方程 填表 回溯Edmonds-Karp 最大流计算题BFS找增广路 残量网络 最大流最小割Johnson 算法选择/判断/计算超级源 → Bellman-Ford → 重新赋权 → Dijkstra × V匈牙利树/二分图匹配算法设计/计算增广路径 Berge’s Lemma DFS线性规划 Simplex计算题标准形式 STF RLF PivotDijkstra vs Bellman-Ford选择/判断适用条件 复杂度 正确性证明Kruskal / Prim计算题贪心 选边/选顶点⭐ 次重点知识点考查形式Master Theorem (3个 Case)选择题BFS/DFS 复杂度 (邻接表 vs 邻接矩阵)选择题QuickSort 划分 (Lomuto/Hoare/Median-of-3)选择题Floyd-Warshall选择/判断Bellman-Ford 检测负环选择/判断OBST 递推公式选择/判断最大流最小割定理选择/填空❌ 不考内容内容说明矩阵运算不做考查Ford-Fulkerson 方法 (非 EK)只考 EKDP AllPathShortPath不要求时间复杂度形式化证明只考 Master Theorem (选择题)贪心算法证明需会分析但不考证明算法设计题答题模板 (20分 × 2)问题分析: 指出属于哪类问题最短路径/最大流/DP/二分图匹配数据结构定义: 说明用什么数据结构存储算法步骤:初始化核心循环/递推终止条件示例运行: 用简单例子展示算法执行过程复杂度分析: 给出时间复杂度和简要解释附常用时间复杂度速查O(1) — 常数时间 O(log n) — 对数时间 (二分查找) O(n) — 线性时间 (遍历) O(n log n) — 线性对数 (排序) O(n²) — 平方时间 (双层循环) O(n³) — 立方时间 (Floyd-Warshall) O(2ⁿ) — 指数时间 (暴力搜索) O(n!) — 阶乘时间 (全排列)算法时间复杂度BFS/DFS (邻接表)O(V E)BFS/DFS (邻接矩阵)O(V²)QuickSort (平均)O(n log n)QuickSort (最坏)O(n²)DijkstraO((VE) log V)Bellman-FordO(V·E)Floyd-WarshallO(V³)JohnsonO(V² log V V·E)KruskalO(E log E)PrimO(E log V)Edmonds-KarpO(V·E²)Hungarian TreeO(V·E)LCSO(m·n)0-1 KnapsackO(n·W)Coin ChangeO(n·amount)OBSTO(n³)Simplex指数级最坏 (但实际高效)拓扑排序O(V E)最后叮嘱: 考试重点是图论问题第 3 章及之后DP Johnson 匈牙利树 线性规划 EK 最大流 MST 是热门考点。算法设计题一定要写出伪代码 示例 复杂度祝考试顺利