算法设计 — 各章知识点总结基于课堂PPT、三次作业、押题文件综合整理。⭐ 考试极端重点 计算/设计大题重点。占位图第1-3讲算法基础与渐进复杂度分析1.1 算法基本概念概念定义算法将输入转化为输出以解决给定问题的一系列计算步骤问题需要寻求答案的提问通用描述实例对问题参数的一组具体赋值参数问题描述中未赋具体值的变量1.2 渐进符号符号含义定义∃c0, n₀, ∀n≥n₀O上界0 ≤ f(n) ≤ c·g(n)Ω下界0 ≤ c·g(n) ≤ f(n)Θ紧致界O ∩ Ωc₁·g(n) ≤ f(n) ≤ c₂·g(n)o非紧致上界lim f(n)/g(n) 0ω非紧致下界lim f(n)/g(n) ∞极限判别法lim 0 → f o(g)即 f O(g) 但 ≠ Θ(g)lim c 0 → f Θ(g)lim ∞ → f ω(g)即 f Ω(g) 但 ≠ Θ(g)重要结论2^(2n) ≠ O(2^n)因为 2(2n)/2n 2^n → ∞1.3 排序算法复杂度算法最好平均最坏空间插入排序Θ(n)Θ(n²)Θ(n²)O(1)选择排序Θ(n²)Θ(n²)Θ(n²)O(1)归并排序Θ(n log n)Θ(n log n)Θ(n log n)O(n)堆排序Θ(n log n)Θ(n log n)Θ(n log n)O(1)1.4 循环不变式三个性质初始化第一次迭代前为真保持若某次迭代前为真则下次迭代前仍为真终止循环结束时不变式给出有用性质通常证明正确性1.5 递归与分治递归三要素Base Case基础情况 Recursive Step递归步骤 问题规模缩小分治三步Divide → Conquer → Combine递归式求解方法方法适用场景代入法猜界后用数学归纳法严格证明考试考7分大题递归树法可视化每层代价等比/等差求和⭐主定理法标准形式 T(n) aT(n/b) f(n)仅考选择题1.6 ⭐ 主定理Master Theorem标准形式T(n) aT(n/b) f(n)其中 a≥1, b1Case条件结论Case 1f(n) O(n^{log_b a - ε})T(n) Θ(n^{log_b a})Case 2f(n) Θ(n^{log_b a}·log^k n)T(n) Θ(n^{log_b a}·log^{k1} n)Case 3f(n) Ω(n^{log_b a ε}) 且 af(n/b) ≤ cf(n), c1T(n) Θ(f(n))正则条件Case 3af(n/b) ≤ cf(n)c 1必须验证不适用情况f(n) 非多项式大于/小于 n^{log_b a}如含 log n 但不是 Case 2 形式1.7 快速排序QuickSort变种Pivot 选择最坏复杂度特点标准快排首/尾元素O(n²)有序数组退化为链Lomuto 分区末尾元素O(n²)慢指针 i 指向 pivot 区域最右端Hoare 分区首/中间元素O(n²)双指针从两端逼近相遇时右指针为分界⭐Median-of-3首/中/尾取中位数O(n log n)有序数组上完美平分Lomuto 分区核心逻辑i 指向小于 pivot 区域的最右端j 遍历数组。遇 A[j] pivot → i 并 swap(A[i], A[j])。最后 swap(A[i1], pivot)。Median-of-3 有序数组上选 n/2 位置为中位数 → 递推式 T(n)2T(n/2)O(n) → Θ(n log n)。M-3 仍可能 O(n²) 的对抗数组构造让每次三数取中的中位数实际是数组第二小/第二大的元素。第4-5讲动态规划DP⭐2.1 DP 核心概念概念定义最优子结构问题最优解包含其子问题的最优解重叠子问题递归过程中同一子问题被多次求解无后效性某阶段状态确定后不受后续决策影响DP 四步骤刻画最优解的结构最优子结构递归定义最优解的值状态转移方程——考试重点自底向上计算最优值填表根据记录信息构造最优解回溯Memoization vs TabulationTop-down (Memoization)Bottom-up (Tabulation)实现递归 缓存迭代 表格求解顺序从大问题出发从小问题出发DP vs 分治 vs 贪心DP分治贪心子问题独立否是—最优子结构需要不一定需要选择可撤销可—不可2.2 FibonacciDP入门朴素递归T(n) O(φⁿ) ≈ O(1.618ⁿ)指数级DP自底向上T(n) O(n)只需记录前两个值 → 空间 O(1)2.3 0/1 背包问题 问题n 件物品每件价值 v_i、重量 w_i背包容量 W每件要么拿要么不拿。最大化总价值。蛮力法O(2ⁿ)状态定义V[i, w] 从前 i 件物品中选、容量为 w 时的最大价值状态转移方程V[i, w] max(V[i-1, w], V[i-1, w-w_i] v_i) if w_i ≤ w V[i, w] V[i-1, w] if w_i w边界V[0, w] 0, V[i, 0] 0DP 表格i0…n 行w0…W 列。时间 Θ(nW)伪多项式空间 Θ(nW)。回溯构造最优解从 V[n, W] 出发若 V[i,w] ≠ V[i-1,w]则物品 i 被选中 → w - w_i, i–否则 i–。2.4 硬币找零Coin Change问题给定面值 coins[] 和金额 amount最少硬币数每种无限。无解返回 -1。状态dp[i] 凑出金额 i 的最少硬币数转移方程dp[i] min(dp[i], dp[i-coin] 1) (i ≥ coin)初始化dp[0]0, 其余∞(amount1)回溯choice[i] 记录达成 dp[i] 最后使用的硬币面值从 amount 倒推。2.5 最长公共子序列LCS定义两字符串 X(m), Y(n)找出最长公共子序列长度。蛮力法X 有 2^m 个子序列检查每个是否属于 Y → O(n·2^m)状态转移方程c[i,j] 0 if i0 or j0 c[i,j] c[i-1,j-1] 1 if x_i y_j c[i,j] max(c[i-1,j], c[i,j-1]) if x_i ≠ y_j回溯b[i,j] 表记录方向↖匹配 / ↑上 / ←左从 b[m,n] 倒推。LCS 不唯一当 c[i-1,j] c[i,j-1] 时存在分支。空间优化只保留当前行和上一行 → O(min(m,n))2.6 最优二叉搜索树OBST问题给定键 K₁…K_n概率 p_i和哑键 D₀…D_n概率 q_i构造 BST 使得期望搜索代价最小。BST 数量n 个键有 Catalan(n) Ω(4ⁿ/n^(3/2)) 种 BST → 蛮力法不可行状态e[i, j] 子树包含键 K_i…K_j 的最小期望搜索代价概率和w[i, j] Σ_{ki}^{j} p_k Σ_{ki-1}^{j} q_k转移方程e[i, j] q_{i-1} if j i-1 e[i, j] min_{i≤r≤j}{e[i,r-1] e[r1,j] w[i,j]} if i ≤ j复杂度O(n³)2.7 贪心算法附问题贪心策略是否最优分数背包按 v_i/w_i 降序选✅0/1 背包按 v_i/w_i 降序选❌需DP活动选择按结束时间最早选✅哈夫曼编码每次合并频率最小的两个✅第6讲-上图论I — MST与最短路 ⭐3.1 图的表示表示存储适合空间邻接矩阵V×邻接表每顶点一个链表稀疏图Θ(VE)3.2 BFS 与 DFSBFSDFS数据结构队列FIFO递归/栈LIFO距离最短路径无权不保证时间戳仅 d[v]d[v]发现 f[v]完成复杂度O(VE)O(VE)DFS 边分类有向图树边v 在发现时为 WHITE返回边v 为 GRAY → 存在环前向边v 为 BLACK 且 u.d v.d交叉边v 为 BLACK 且 u.d v.d无向图特殊性只有树边和返回边无前向边和交叉边。括号定理[u.d, u.f] 和 [v.d, v.f] 要么不相交要么一个完全包含另一个。白路径定理v 是 u 的后代 ⟺ 发现 u 时存在从 u 到 v 的全白顶点路径。拓扑排序仅 DAG按 f[v] 降序排列 / Kahn 算法不断移除入度为 0 的节点。Θ(VE)。强连通分量SCC在 G^T 上按 f 降序运行 DFS每棵 DFS 树 一个 SCC。Θ(VE)。3.3 最小生成树MST安全边定理Theorem 23.1设 A 是某棵 MST 的子集(X, Y) 是尊重 A 的割(u, v) 是跨越该割的轻边 → (u, v) 是 A 的安全边。术语定义割V 划分为 X 和 Y V-X跨越边一端在 X一端在 Y尊重没有边跨越 A轻边跨越该割的权重最小的边推论 23.2连接森林中一个连通分量到其余顶点的轻边是安全边。MST 性质最小权边一定属于某棵 MST若所有边权重互不相同 → MST 唯一不同 MST 的边权重排序列表相同生成树有 |V|-1 条边KruskalO(E log E)按权重升序排序所有边初始化并查集每个顶点独立成树遍历每条边 (u,v)若 u,v 在不同集合 → 选中该边union(u,v)直到选中 |V|-1 条边PrimO(E log V)key[r]0, 其余 key[v]∞每次从 Q优先队列中取 key 最小的 u将其加入 MST更新 u 的所有邻居 v若 w(u,v) key[v] → key[v]w(u,v), π[v]u对比Kruskal 适合稀疏图 |E|≈|V|Prim 适合稠密图 |E|≈|V|²3.4 最短路径基本概念最优子结构Lemma 24.1最短路径的子路径也是最短路径。松弛操作if d[v] d[u] w(u,v): d[v] d[u] w(u,v) π[v] u松弛性质性质内容三角不等式δ(s,v) ≤ δ(s,u) w(u,v)上界性质d[v] ≥ δ(s,v)一旦相等永不改变收敛性质若 s⇝u→v 是最短路且 d[u]δ(s,u)松弛 (u,v) 后 d[v]δ(s,v)路径松弛性质按最短路顺序松弛边可精确得到所有距离3.5 Bellman-Ford 算法时间复杂度O(VE)核心V-1 轮每轮松弛所有边。第 k 轮后所有长度 ≤ k 的最短路径被正确计算最多 V-1 条边 → V-1 轮负环检测第 V 轮仍可松弛 → 存在可达负权环返回 FALSE。提前停止优化若某轮无任何 d[v] 更新提前终止。3.6 DAG 最短路径拓扑排序 按拓扑序松弛每条边。O(VE)。局限必须有向无环图无法处理循环依赖。3.7 Dijkstra 算法 条件所有边权 ≥ 0不满足此条件不能用核心贪心策略——每次从 Q 中取 d[v] 最小的顶点加入 S松弛其所有出边。循环不变式每次 while 开始时∀v∈S, d[v]δ(s,v)。复杂度二叉堆O((VE) log V) O(E log V)斐波那契堆O(V log V E)3.8 最短路算法对比算法复杂度负权边检测负环适用图DAG 拓扑松弛O(VE)✅—仅 DAGDijkstraO(E log V)❌—非负权图Bellman-FordO(VE)✅✅任意图第6讲-下图论II — 全源最短路、流与匹配 ⭐4.1 Floyd-Warshall 算法类型DP 求解全源最短路径核心思想依次允许使用顶点 {1,2,…,k} 作为中间顶点。DP 递推d^{(k)}_{ij} w_{ij} (k0) d^{(k)}_{ij} min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} d^{(k-1)}_{kj}) (k≥1)前驱矩阵π⁽⁰⁾_{ij} i若存在边 i→j否则 NILπ⁽ᵏ⁾{ij} π⁽ᵏ⁻¹⁾{kj}若经过 k 更短否则 π⁽ᵏ⁻¹⁾_{ij}复杂度Θ(V³)三重循环 k→i→j。空间 Θ(V²)。负环检测算法结束后检查对角线 d_{ii}若 d_{ii} 0 → 存在负权环。考试技巧k1 和 kn 时可用瞪眼法直接判断第一行/第n行不需更新当中间值 b 0 或无穷时不用更新abc 不会变小4.2 Johnson 算法 动机Dijkstra 不能处理负权边但 Johnson 通过势能变换将负权转为非负再多次调用 Dijkstra。五步流程添加超级源点 S连接 S 到所有顶点边权 0运行 Bellman-Ford从 S 出发得到 h(v) δ(S, v)重新赋权ŵ(u,v) w(u,v) h(u) - h(v)保证 ≥ 0对每个顶点 u 运行 Dijkstra在 ŵ 上得到 δ̂(u,v)恢复真实距离δ(u,v) δ̂(u,v) h(v) - h(u)注意后减前重赋权引理Lemma 25.1p 在 w 下是最短路 ⟺ p 在 ŵ 下是最短路G 在 w 下有负环 ⟺ G 在 ŵ 下有负环复杂度O(VE V² log V)稀疏图优于 Floyd-Warshall4.3 最大流问题流网络三约束容量约束0 ≤ f(u,v) ≤ c(u,v)流量守恒Σ f(u,v) Σ f(v,u)∀v ≠ s,t反对称性f(u,v) -f(v,u)4.4 Edmonds-Karp 算法 定义Ford-Fulkerson 方法的一种实现——每次用 BFS 找最短增广路径按边数最少。三大核心概念① 残量网络Residual Network正向剩余容量c(u,v) - f(u,v)反向边容量f(u,v)允许反悔退流② 增广路径Augmenting Path残量网络中从 s 到 t 的一条路径瓶颈容量 路径上最小剩余容量沿路径推进瓶颈流量正向-反向③ 最小割Min Cut割 (S, T)S 含 sT 含 t割容量 Σ_{u∈S,v∈T} c(u,v)最大流最小割定理max flow min cut capacity算法流程初始化 f(u,v) 0在残量网络中 BFS 寻找 s→t 最短路找到 → 推进瓶颈流量更新残量网络重复 2找不到 → 终止当前流 最大流S BFS 可达的所有顶点 最小割复杂度O(VE²)4.5 二分图匹配 — 匈牙利树算法 关键定义匹配边集 M任意两条边无公共顶点最大匹配边数最多的匹配交替路径交替经过匹配边和非匹配边的路径增广路径起点和终点均为未匹配顶点的交替路径Berge 引理M 是最大匹配 ⟺ 不存在 M-增广路径。匈牙利树算法初始化 M ∅或从任意合法匹配开始从左侧未匹配节点出发DFS/BFS 搜索增广路径找到增广路径 →翻转路径上的边匹配↔非匹配匹配数 1重复直到找不到增广路径复杂度O(VE)可从任意匹配开始算法会自动修正前期不合理的匹配递归回溯腾位置。第7讲线性规划LP⭐5.1 基本概念标准形式最大化c^T x 约束 Ax ≤ b x ≥ 0三要素最大化目标、≤ 不等式约束、变量非负。5.2 标准化转换 ⭐原始形式转换方法最小化 z最大化 -z等式 a^Tx b拆为 a^Tx ≤ b 和 -a^Tx ≤ -ba^Tx ≥ b乘 -1 → -a^Tx ≤ -b自由变量 x_ix_i x_i⁺ - x_i⁻x_i⁺, x_i⁻ ≥ 05.3 松弛形式对每个不等式 Σ a_ij x_j ≤ b_i引入松弛变量s_i ≥ 0Σ a_ij x_j s_i b_i基本变量B等式左侧变量初始为松弛变量非基本变量N等式右侧变量初始为原变量初始解所有 NB 0 → 所有 B 对应 b_i 值。5.4 单纯形算法Simplex⭐核心思想沿凸多面体的边从一个顶点走到另一个顶点每次增加目标值。一轮迭代三步① STF——选择进入变量Select Target Function在目标函数中选择系数最大的正数NB 变量 x_e 进基。② RLF——选择离开变量Ratio Limit Function对每个约束计算 x_e 能增加多少若系数 a_{ie} ≤ 0 → 该约束不限制 x_e 增长若 a_{ie} 0 → 上限 b_i / a_{ie}选上限最小的那个约束对应的 B 变量 x_l 出基。③ 转轴操作Pivot约束行 l将 x_e 表达为 NB 变量其他行将 x_e 的表达式代入消除 x_e目标函数同样代入更新系数x_e 变为 B 变量x_l 变为 NB 变量终止条件目标函数中所有 NB 变量系数 ≤ 0 → 达到最优解。无界判定存在 NB 变量系数 0 但其在所有约束中系数 ≤ 0 → 无界解。几何解释每个顶点 一个基本可行解沿边移动 转轴操作顶点个数有限 → 必然终止。5.5 复杂度与注意事项最坏指数时间但实际中非常高效内点法椭球法多项式时间 O(n³L)5.6 对偶性简标准形 LP 的对偶原问题变量数 n约束数 m → 对偶变量数 m约束数 n原问题是 max → 对偶问题是 min弱对偶定理对偶可行解值 ≥ 原问题可行解值强对偶定理一个最优时另一个也最优且目标值相等附一全部算法时间复杂度速查表算法时间复杂度关键原因插入排序最坏Θ(n²)每个元素可能要移到最前面归并排序Θ(n log n)T(n)2T(n/2)Θ(n)主定理 Case 2快速排序最坏Θ(n²)退化链 T(n)T(n-1)Θ(n)快速排序平均Θ(n log n)平衡划分 T(n)2T(n/2)Θ(n)M-3快排有序Θ(n log n)中位数居中完美平分Fibonacci DPO(n)每个子问题只算一次0/1背包DPΘ(nW)填 n×W 表伪多项式LCSDPΘ(mn)填 m×n 表OBSTDPO(n³)三重循环 i/j/rBFS / DFSO(VE)每个顶点每条边处理一次拓扑排序Θ(VE)DFS 按 f 降序SCCKosarajuΘ(VE)两次 DFSKruskalO(E log E)排序边 并查集 O(1)Prim二叉堆O(E log V)E 次 decrease-key每次 log VBellman-FordO(VE)V-1轮 × E 条边DAG 最短路O(VE)拓扑排序 边松弛Dijkstra二叉堆O(E log V)V 次 extract-min E 次 decrease-keyFloyd-WarshallΘ(V³)三重循环 k→i→jJohnsonO(VE V² log V)1×BF V×DijkstraEdmonds-KarpO(VE²)最多 VE 次增广匈牙利树O(VE)每个顶点一次 DFS/BFS 搜索增广路Simplex指数最坏实践中多 O(mn)附二押题对照确认押题重要性笔记位置主定理选择题⭐§1.6DP 状态转移方程 填表大题§2.3-2.6Johnson 多元最短路大题§4.2匈牙利树/二分图匹配大题§4.5线性规划/单纯形法大题§5.4EK 增广路/最大流大题§4.4Kruskal / Prim大题§3.3Dijkstra基础必备§3.7Bellman-Ford基础必备§3.5Floyd-Warshall小题§4.1霍夫曼编码小题§2.7DAG 拓扑排序小题§3.2