算法设计 — 全部算法伪代码与解释

算法设计 — 全部算法伪代码与解释为考试最后两道算法设计大题准备。伪代码可用中文描述重点是逻辑清晰、步骤完整。占位图一、排序与划分算法1.1 Lomuto 分区QuickSort 核心思想选末尾元素为 pivot慢指针 i 指向小于 pivot 区域的最右端快指针 j 遍历数组。遇 A[j] pivot 时 i 并交换。算法 Lomuto-Partition(A, low, high) 输入: 数组A, 起始索引low, 结束索引high 输出: pivot的最终位置 1. pivot A[high] 2. i low - 1 // i指向小于pivot区域的最右端 3. for j low to high-1: 4. if A[j] pivot: 5. i i 1 6. swap(A[i], A[j]) 7. swap(A[i1], A[high]) // 将pivot放到正确位置 8. return i 1复杂度每次分区 O(n)总复杂度取决于递归深度。1.2 Hoare 分区思想双指针从两端逼近。左指针找 ≥ pivot 的元素右指针找 ≤ pivot 的元素找到后交换。指针交错时右指针指向分界。算法 Hoare-Partition(A, low, high) 输入: 数组A, 起始索引low, 结束索引high 输出: 分界索引j左半部分≤pivot右半部分≥pivot 1. pivot A[low] // 选首元素为pivot 2. i low - 1 3. j high 1 4. while true: 5. do i i 1 while A[i] pivot // 找左边≥pivot的元素 6. do j j - 1 while A[j] pivot // 找右边≤pivot的元素 7. if i j: return j // 指针相遇/交错返回分界 8. swap(A[i], A[j])注意Hoare 分区后 pivot不保证在最终位置会随递归逐步沉淀。1.3 Median-of-3 快速排序思想选首、中、尾三个元素的中位数作为 pivot避免有序数组上退化。算法 Median-of-3-QuickSort(A, low, high) 输入: 数组A, 起始索引low, 结束索引high 1. if low high: 2. // 三数取中 3. mid (low high) / 2 4. if A[mid] A[low]: swap(A[low], A[mid]) 5. if A[high] A[low]: swap(A[low], A[high]) 6. if A[high] A[mid]: swap(A[mid], A[high]) 7. swap(A[mid], A[high]) // 将中位数放到末尾作为pivot 8. 9. pi Lomuto-Partition(A, low, high) 10. Median-of-3-QuickSort(A, low, pi-1) 11. Median-of-3-QuickSort(A, pi1, high)复杂度最坏/平均 Θ(n log n)在有序数组上也 Θ(n log n)。二、图遍历算法2.1 BFS广度优先搜索思想队列实现逐层向外扩展。维护 color白/灰/黑、距离 d、前驱 π。算法 BFS(G, s) 输入: 图G(邻接表), 源点s 输出: 每个顶点的最短距离d[v]和前驱π[v] 1. for 每个顶点 v ∈ V[G] - {s}: 2. color[v] WHITE; d[v] ∞; π[v] NIL 3. color[s] GRAY; d[s] 0; π[s] NIL 4. Q ∅; Enqueue(Q, s) 5. while Q ≠ ∅: 6. u Dequeue(Q) 7. for 每个 v ∈ Adj[u]: 8. if color[v] WHITE: 9. color[v] GRAY 10. d[v] d[u] 1 11. π[v] u 12. Enqueue(Q, v) 13. color[u] BLACK复杂度O(VE)。每个顶点入队一次每条边被检查一次。2.2 DFS深度优先搜索思想递归/栈实现深入到底再回溯。记录发现时间 d[v] 和完成时间 f[v]。算法 DFS(G) 输入: 图G 输出: 各顶点的d[v], f[v], π[v] 1. for 每个顶点 v ∈ V[G]: 2. color[v] WHITE; π[v] NIL 3. time 0 4. for 每个顶点 v ∈ V[G]: 5. if color[v] WHITE: 6. DFS-Visit(v) 子过程 DFS-Visit(u): 1. color[u] GRAY 2. time time 1; d[u] time 3. for 每个 v ∈ Adj[u]: 4. if color[v] WHITE: 5. π[v] u 6. DFS-Visit(v) 7. color[u] BLACK 8. time time 1; f[u] time复杂度O(VE)边分类有向图遇 WHITE →树边遇 GRAY →返回边说明有环遇 BLACK 且 d[u] d[v] →前向边遇 BLACK 且 d[u] d[v] →交叉边2.3 拓扑排序思想方法一DFS 后按完成时间 f[v]降序排列。方法二Kahn 算法不断移除入度为 0 的节点。算法 Topological-Sort-DFS(G) 输入: 有向无环图G 输出: 拓扑排序序列链表 1. 调用 DFS(G)计算每个顶点的完成时间 f[v] 2. 每当一个顶点完成变 BLACK将其插入链表头部 3. return 链表算法 Kahn-Topological-Sort(G) 输入: 有向无环图G 输出: 拓扑排序队列 1. 计算所有顶点的入度 indegree[v] 2. Q 空队列 3. for 每个 v: if indegree[v]0: Enqueue(Q, v) 4. while Q ≠ ∅: 5. u Dequeue(Q); 输出 u 6. for 每个(u,v)∈E: 7. indegree[v]-- 8. if indegree[v]0: Enqueue(Q, v)复杂度Θ(VE)三、最小生成树MST⭐3.1 Kruskal 算法思想按边权重升序处理每条边用并查集判断两端是否已在同一连通分量。不是则将边加入 MST。算法 Kruskal(G) 输入: 连通无向图G(V,E)每条边有权重w 输出: 最小生成树的边集A 1. A ∅ 2. for 每个顶点 v ∈ V: 3. Make-Set(v) // 每个顶点独立成集合 4. 将E中所有边按权重w升序排序 5. for 每条边(u,v) ∈ E按升序: 6. if Find-Set(u) ≠ Find-Set(v): // 不在同一集合→不成环 7. A A ∪ {(u, v)} 8. Union(u, v) // 合并两个集合 9. return A并查集两个关键函数Find-Set(x)返回 x 所在集合的代表元路径压缩优化Union(x, y)将两个集合合并按秩合并优化复杂度O(E log E) O(E log V)3.2 Prim 算法思想从任意起点出发维护已选顶点集 X每次选连接 X 和 V-X 的最小权边将新顶点加入 X。算法 Prim(G, r) 输入: 连通无向图G, 起始顶点r 输出: 最小生成树的边集A 1. for 每个 v ∈ V: 2. key[v] ∞ 3. π[v] NIL 4. key[r] 0 5. Q V // 所有顶点放入优先队列 6. while Q ≠ ∅: 7. u Extract-Min(Q) // 取key最小的顶点 8. for 每个 v ∈ Adj[u]: 9. if v ∈ Q and w(u,v) key[v]: 10. π[v] u 11. key[v] w(u,v) // Decrease-Key操作 12. // 从π数组恢复MST边集: A {(v, π[v]) | v ≠ r} 13. return A复杂度二叉堆 O(E log V)斐波那契堆 O(E V log V)四、最短路径算法 ⭐4.1 Dijkstra 算法思想贪心策略每次从优先队列中取 d[v] 最小的顶点加入已确定集 S松弛其所有出边。仅适用于非负权图。算法 Dijkstra(G, w, s) 输入: 图G, 边权函数w(所有w≥0), 源点s 输出: 最短距离d[v]和前驱π[v] 1. for 每个 v ∈ V: 2. d[v] ∞; π[v] NIL 3. d[s] 0 4. S ∅ // 已确定最短距离的顶点集 5. Q V // 优先队列按d值排序 6. while Q ≠ ∅: 7. u Extract-Min(Q) // 取d值最小的顶点 8. S S ∪ {u} 9. for 每个 v ∈ Adj[u]: 10. if d[v] d[u] w(u,v): // 松弛操作 11. d[v] d[u] w(u,v) 12. π[v] u 13. return (d, π)复杂度二叉堆 O((VE)log V)斐波那契堆 O(V log V E)考试答题要点必须说明维护 S 集合已确定和 Q 优先队列待处理每次展示 d[v] 和 π[v] 的变化。4.2 Bellman-Ford 算法思想进行 V-1 轮每轮松弛所有边。第 k 轮后所有长度 ≤ k 的最短路被正确计算。第 V 轮仍可松弛说明存在负环。算法 Bellman-Ford(G, w, s) 输入: 图G, 边权函数w(可为负), 源点s 输出: 最短距离d[v], 前驱π[v]; 或报告存在负权环 1. for 每个 v ∈ V: 2. d[v] ∞; π[v] NIL 3. d[s] 0 4. for i 1 to |V|-1: // V-1轮 5. for 每条边(u,v) ∈ E: 6. if d[v] d[u] w(u,v): // 松弛 7. d[v] d[u] w(u,v) 8. π[v] u 9. for 每条边(u,v) ∈ E: // 检测负环 10. if d[v] d[u] w(u,v): 11. return 存在可达负权环 12. return (d, π)复杂度O(VE)为什么 V-1 轮任意不含环的最短路径最多含 |V|-1 条边每轮至少确定一条边上的最短距离。4.3 DAG 最短路径思想先拓扑排序确定处理顺序再按拓扑序依次松弛每个顶点的出边。一次遍历即可。算法 DAG-Shortest-Path(G, w, s) 输入: 有向无环图G, 边权函数w, 源点s 输出: 最短距离d[v], 前驱π[v] 1. 对G进行拓扑排序得到顶点序列 2. for 每个 v ∈ V: 3. d[v] ∞; π[v] NIL 4. d[s] 0 5. for 每个顶点 u按拓扑序: 6. for 每个 v ∈ Adj[u]: 7. if d[v] d[u] w(u,v): // 松弛 8. d[v] d[u] w(u,v) 9. π[v] u 10. return (d, π)复杂度O(VE)4.4 Floyd-Warshall 算法思想DP 求解全源最短路径。依次允许中间顶点 k1,2,…,n检查经过 k 是否更短。算法 Floyd-Warshall(W) 输入: 权值矩阵W (W[i][j]边权, 无边∞, W[i][i]0) 输出: 最短距离矩阵D和前驱矩阵Π 1. n W的行数 2. D⁽⁰⁾ W 3. for i 1 to n: // 初始化前驱矩阵 4. for j 1 to n: 5. if i≠j and W[i][j] ∞: 6. Π[i][j] i 7. else: 8. Π[i][j] NIL 9. for k 1 to n: // 依次允许顶点1..k为中转站 10. for i 1 to n: 11. for j 1 to n: 12. if D[i][k] D[k][j] D[i][j]: 13. D[i][j] D[i][k] D[k][j] 14. Π[i][j] Π[k][j] // 经过k下一跳从k走 15. return (D, Π)复杂度Θ(n³)检测负环算法结束后检查对角线 D[i][i] 0 则存在负环。4.5 Johnson 算法 押题重点思想引入势能函数 h(v) 将负权边转化为非负再对每个顶点运行 Dijkstra最后恢复真实距离。算法 Johnson(G, w) 输入: 图G(V,E), 边权函数w(可为负, 但不能有负环) 输出: 所有点对的最短距离矩阵D (D[u][v]δ(u,v)) // 步骤1: 添加超级源点 1. 创建新图G (V∪{s}, E∪{(s,v):v∈V}) 2. for 每个 v ∈ V: w(s,v) 0 // 步骤2: Bellman-Ford 计算势能 3. if Bellman-Ford(G, w, s) 检测到负环: 4. return 存在负权环 5. for 每个 v ∈ V: 6. h(v) d[v] // 势能函数 h(v) δ(s,v) // 步骤3: 重新赋权使所有边权非负 7. for 每条边(u,v) ∈ E: 8. ŵ(u,v) w(u,v) h(u) - h(v) // 由三角不等式保证≥0 // 步骤4: 对每个顶点运行Dijkstra 9. for 每个顶点 u ∈ V: 10. 运行 Dijkstra(G, ŵ, u)得到 δ̂(u,v) for all v 11. for 每个顶点 v ∈ V: 12. D[u][v] δ̂(u,v) h(v) - h(u) // 恢复真实距离 13. return D重赋权公式ŵ(u,v) w(u,v) h(u) - h(v)恢复公式δ(u,v) δ̂(u,v) h(v) - h(u)注意后减前复杂度O(VE V² log V)。稀疏图优于 Floyd-Warshall。五、最大流算法 ⭐5.1 Edmonds-Karp 算法思想在残量网络中用BFS寻找最短增广路径沿路径推进瓶颈流量反复直到无增广路。算法 Edmonds-Karp(G, c, s, t) 输入: 流网络G, 容量函数c, 源点s, 汇点t 输出: 最大流f 1. for 每条边(u,v) ∈ E: 2. f(u,v) 0 // 初始化流为0 3. while true: 4. // 在残量网络中BFS寻找s→t最短增广路径 5. (augPath, bottleneck) BFS-Residual(G, c, f, s, t) 6. if augPath NIL: 7. break // 无增广路已得最大流 8. // 沿增广路径推进瓶颈流量 9. for 每条边(u,v) ∈ augPath: 10. f(u,v) f(u,v) bottleneck // 正向加 11. f(v,u) f(v,u) - bottleneck // 反向减允许反悔 12. return fBFS-Residual 子过程子过程 BFS-Residual(G, c, f, s, t) 输出: (增广路径, 瓶颈容量) 或 (NIL, 0) 1. for 每个v: color[v]WHITE; π[v]NIL 2. color[s]GRAY; Q{s} 3. while Q≠∅: 4. u Dequeue(Q) 5. for 每个v∈Adj[u]: 6. // 检查残量网络中的边正向或反向 7. residual c(u,v) - f(u,v) // 正向剩余容量 8. if residual 0 and color[v]WHITE: 9. color[v]GRAY; π[v]u 10. cf[v] min(cf[u], residual) // 更新瓶颈 11. if vt: goto 重建路径 12. Enqueue(Q, v) 13. color[u]BLACK 14. if π[t]NIL: return (NIL, 0) // t不可达 15. // 重建路径 16. 从t沿π回溯到s, 得到路径P 17. return (P, cf[t])复杂度O(VE²)最小割算法终止时 S {BFS 可达的所有顶点}(S, V-S) 即为最小割。六、二分图匹配 — 匈牙利树算法 ⭐6.1 匈牙利树算法思想从左侧未匹配节点出发在二分图中搜索增广路径起点终点均为未匹配节点路径交替经过非匹配边和匹配边。找到后翻转路径上的边使匹配数 1。算法 Hungarian-Matching(G) 输入: 二分图G(L∪R, E) 输出: 最大匹配M 1. M ∅ // 初始匹配为空 2. for 每个顶点 u ∈ L: 3. // 以u为根构建匈牙利树寻找增广路径 4. 将所有顶点标记为未访问 5. augPath Find-Augmenting-Path(G, M, u) 6. if augPath ≠ NIL: 7. // 翻转增广路径上的边 8. for 路径上的每条边 e: 9. if e ∈ M: M M - {e} // 原匹配边→非匹配 10. else: M M ∪ {e} // 原非匹配边→匹配 11. return MFind-Augmenting-Path 子过程DFS 版本子过程 Find-Augmenting-Path(G, M, u) 输入: 二分图G, 当前匹配M, 起点u(左侧未匹配节点) 输出: 增广路径 或 NIL 1. if u 在左侧: 2. for 每个 v ∈ Adj[u]右侧邻居: 3. if v 未被访问: 4. 标记v为已访问 5. if v 未匹配: 6. return [u → v] // 找到增广路径 7. else: 8. // v已匹配尝试让v的匹配对象换人 9. w v的匹配对象(M中与v匹配的顶点) 10. subPath Find-Augmenting-Path(G, M, w) 11. if subPath ≠ NIL: 12. return [u → v] subPath // 拼接路径 13. return NIL复杂度O(VE)。每个左侧顶点最多一次搜索每次搜索 O(E)。考试答题要点说清从空集或任意匹配开始展示每次搜索到的增广路径展示翻转后的匹配集 M引用 Berge 引理M 最大 ⟺ 无增广路径七、动态规划DP⭐7.1 0/1 背包问题思想二维 DPV[i,w] 表示前 i 件物品在容量 w 下的最大价值。算法 01-Knapsack(values, weights, W) 输入: 价值数组v[1..n], 重量数组w[1..n], 容量W 输出: 最大总价值及选中的物品集合 // 步骤1: 填DP表 1. 创建二维数组 V[0..n][0..W] 2. for j 0 to W: V[0][j] 0 // 无物品→价值0 3. for i 1 to n: 4. for j 0 to W: 5. if w[i] j: // 装不下 6. V[i][j] V[i-1][j] 7. else: // 能装下选max(不拿, 拿) 8. V[i][j] max(V[i-1][j], V[i-1][j-w[i]] v[i]) // 步骤2: 回溯构造解 9. selected [] 10. i n; j W 11. while i 0 and j 0: 12. if V[i][j] ≠ V[i-1][j]: // 物品i被选中 13. selected.append(i) 14. j j - w[i] 15. i i - 1 16. return (V[n][W], selected)状态转移方程dp[i][w] max(dp[i-1][w], dp[i-1][w-w_i] v_i) (w_i ≤ w) dp[i][w] dp[i-1][w] (w_i w)复杂度Θ(nW)伪多项式7.2 硬币找零Coin Change思想一维 DPdp[i] 凑出金额 i 的最少硬币数。每种硬币无限使用。算法 Coin-Change(coins, amount) 输入: 硬币面值数组coins[1..k], 目标金额amount 输出: 最少硬币数 和 具体硬币组合 1. dp[0..amount] ∞ // 初始化为无穷 2. dp[0] 0 3. parent[0..amount] -1 // 用于回溯记录最后使用的硬币 4. for i 1 to amount: 5. for 每种硬币 coin ∈ coins: 6. if i ≥ coin and dp[i-coin] 1 dp[i]: 7. dp[i] dp[i-coin] 1 8. parent[i] coin // 记录到达i的最后一步用了coin // 回溯构造解 9. if dp[amount] ∞: return -1 // 无解 10. result [] 11. curr amount 12. while curr 0: 13. coin parent[curr] 14. result.append(coin) 15. curr curr - coin 16. return (dp[amount], result)状态转移方程dp[i] min(dp[i], dp[i-coin] 1)复杂度O(n × amount)7.3 最长公共子序列LCS思想二维 DPc[i,j] X[1…i] 和 Y[1…j] 的 LCS 长度。算法 LCS(X, Y) 输入: 字符串X(长度m), 字符串Y(长度n) 输出: LCS长度 和 LCS本身 // 步骤1: 填表 1. 创建二维数组 c[0..m][0..n], 方向数组 b[0..m][0..n] 2. for i 0 to m: c[i][0] 0 3. for j 0 to n: c[0][j] 0 4. for i 1 to m: 5. for j 1 to n: 6. if X[i] Y[j]: 7. c[i][j] c[i-1][j-1] 1 8. b[i][j] ↖ // 匹配沿对角线 9. else if c[i-1][j] ≥ c[i][j-1]: 10. c[i][j] c[i-1][j] 11. b[i][j] ↑ // 取上方 12. else: 13. c[i][j] c[i][j-1] 14. b[i][j] ← // 取左方 // 步骤2: 回溯构造LCS 15. Print-LCS(b, X, i, j): 16. if i0 or j0: return 17. if b[i][j] ↖: 18. Print-LCS(b, X, i-1, j-1) 19. 输出 X[i] 20. else if b[i][j] ↑: 21. Print-LCS(b, X, i-1, j) 22. else: 23. Print-LCS(b, X, i, j-1)状态转移方程c[i,j] c[i-1,j-1] 1 (X[i]Y[j]) c[i,j] max(c[i-1,j], c[i,j-1]) (X[i]≠Y[j])复杂度Θ(mn)7.4 最优二叉搜索树OBST思想二维 DPe[i,j] 子树包含键 K_i…K_j 的最小期望搜索代价。算法 OBST(p, q, n) 输入: p[1..n]键的概率, q[0..n]哑键的概率 输出: 最小期望搜索代价 和 根表root 1. 创建表 e[1..n1][0..n], w[1..n1][0..n], root[1..n][1..n] 2. for i 1 to n1: 3. e[i][i-1] q[i-1] // 空子树只有哑键 4. w[i][i-1] q[i-1] 5. for l 1 to n: // l: 子树中键的数量 6. for i 1 to n-l1: 7. j i l - 1 8. e[i][j] ∞ 9. w[i][j] w[i][j-1] p[j] q[j] 10. for r i to j: // 尝试每个键作为根 11. t e[i][r-1] e[r1][j] w[i][j] 12. if t e[i][j]: 13. e[i][j] t 14. root[i][j] r 15. return (e[1][n], root)状态转移方程e[i,j] min_{i≤r≤j}{e[i,r-1] e[r1,j] w[i,j]}复杂度O(n³)八、线性规划 — 单纯形法 ⭐8.1 单纯形法Simplex思想从可行域的一个顶点基本可行解出发沿边移动到相邻顶点每次增加目标值直到最优。算法 Simplex(A, b, c) 输入: 约束矩阵A[m×n], 常数向量b[m], 目标系数c[n] (标准形: max c^Tx, Ax≤b, x≥0) 输出: 最优解x 和 最优目标值z // 步骤0: 转换为松弛形式 1. 引入松弛变量 x_{n1}...x_{nm}将 Ax≤b 转为: x_{ni} b_i - Σ_{j1}^{n} a_{ij}·x_j (i1..m) 2. 目标函数: z Σ_{j1}^{n} c_j·x_j 3. NB变量集 {1..n} (右侧), B变量集 {n1..nm} (左侧) // 步骤1: 主循环 4. while 目标函数中存在系数 0 的NB变量: 5. // STF: 选择进入变量 6. 选 x_e: c_e max{c_j | c_j 0} 所在的NB变量 7. if 所有约束中a_{ie} ≤ 0: 8. return 无界解 9. // RLF: 选择离开变量最小比率检验 10. minRatio ∞ 11. for i 1 to m: 12. if a_{ie} 0: 13. ratio b_i / a_{ie} 14. if ratio minRatio: 15. minRatio ratio 16. l i // 第l个约束的B变量出基 17. // Pivot: 转轴操作 18. 解第l个约束: x_e (b_l - Σ_{j≠e}a_{lj}·x_j - x_{B_l}) / a_{le} 19. 将x_e代入所有其他约束和目标函数 20. 将x_e加入B变量集将原x_{B_l}加入NB变量集 21. return (x*, z*)STF 规则选目标函数中正系数最大的 NB 变量进基。RLF 规则选 b_i / a_{ie}最小正值对应的 B 变量出基。最优性条件目标函数中所有 NB 变量系数 ≤ 0。复杂度最坏指数时间实践中通常高效。附算法设计题答题模板考试最后一题要求写出完整的算法设计建议按以下模板作答算法名称XXXX 算法 问题描述 用自己的话简述要解决的问题 设计思路 1-2句说明核心策略贪心DP图论转化 数据结构 列出要用到的关键数据结构及其作用 伪代码 按上面各算法的格式写出中文注释即可 复杂度分析 时间复杂度O(XXX)原因…… 空间复杂度O(XXX)原因…… 正确性简述 关键定理/性质如Dijkstra基于贪心选择性质和最优子结构、 匈牙利基于Berge引理——无增广路则为最大匹配全部算法复杂度速查算法时间空间用途QuickSort (M-3)Θ(n log n)O(log n)排序BFSO(VE)O(V)无权最短路DFSO(VE)O(V)遍历/拓扑/SCCKruskalO(E log E)O(V)MST稀疏Prim (二叉堆)O(E log V)O(V)MST稠密Dijkstra (二叉堆)O(E log V)O(V)单源最短路非负Bellman-FordO(VE)O(V)单源最短路含负Floyd-WarshallΘ(V³)Θ(V²)全源最短路JohnsonO(VEV²logV)O(V²)全源最短路稀疏Edmonds-KarpO(VE²)O(VE)最大流匈牙利树O(VE)O(VE)二分图最大匹配01背包DPΘ(nW)Θ(nW)组合优化LCS DPΘ(mn)Θ(mn)序列比较OBST DPO(n³)O(n²)最优搜索树Simplex指数最坏O(mn)线性规划