如果你正在准备算法设计与分析这门课或者刷题时总觉得“看答案懂、自己写就废”那大概率不是编程语言的问题而是算法设计与分析的主线没有串起来。算法设计负责把一个模糊问题变成可执行的求解过程算法分析负责判断这个过程正不正确、快不快、在数据规模变大时会不会崩。我见过太多同学把分治、动态规划、贪心、回溯当成互不相干的章节背考试时一遇到新题就无从下手。这篇知识点总结按我平时复习和带人刷题的顺序整理从复杂度分析、经典设计策略到图算法、字符串、排序和期末编程题尽量把“为什么这么设计”和“实际怎么写”都讲透。适合刚入门、准备期末、考研复试或者想补基础的朋友。1. 算法设计与分析到底在学什么1.1 从问题到程序的四步闭环很多人学算法设计与分析习惯一上来就看代码。这个顺序其实反了。拿到一个问题第一步是问题建模把现实描述转成输入、输出、约束和目标。比如“安排教室”要转成区间调度“找最短路线”要转成带权图最短路。第二步才是算法设计选择分治、动态规划、贪心、回溯还是图算法。第三步是正确性证明说明算法为什么一定能得到可行解以及为什么是最优解或满足要求。第四步是复杂度分析估计算法和额外空间随着输入规模怎么增长。这四步里最容易丢分的是正确性证明和复杂度分析。代码写出来只能说明你会实现不能说明你懂算法。比如贪心算法写起来往往比动态规划短但难点在证明“局部最优能推出全局最优”。交换论证、数学归纳、反证法是常用工具。动态规划则要证明状态定义无后效性转移方程覆盖所有情况。期末编程题可能不要求写完整证明但选择题、简答题和设计题经常考这些。我自己的习惯是每学一个新算法都在纸上写三行它解决什么问题核心操作是什么复杂度卡在哪里。比如归并排序解决排序问题核心操作是合并两个有序数组复杂度卡在递归树每层 O(n)、共 O(log n) 层所以是 O(n log n)。这三行写顺了比死记代码有用得多。1.2 复杂度分析大O、大Ω、大Θ和均摊复杂度分析不是算精确时间而是看增长趋势。大O表示上界大Ω表示下界大Θ表示紧确界。平时说“这个算法是 O(n log n)”意思是最坏情况下不会超过 n log n 这个量级但不代表它一定跑得慢。常数因子、缓存友好性、语言实现也会影响真实速度不过考试和理论分析先看渐进阶。常见阶从低到高可以记成O(1) O(log n) O(n) O(n log n) O(n^2) O(n^3) O(2^n) O(n!)。二分查找是 O(log n)归并排序和堆排序是 O(n log n)冒泡、插入、选择排序是 O(n^2)全排列枚举是 O(n!)。指数级和阶乘级算法只能处理很小的规模工程里通常要换策略或者用剪枝、近似。均摊分析容易被忽略。动态数组扩容时单次扩容是 O(n)但连续插入 n 次的均摊代价是 O(1)。并查集按秩合并加路径压缩后均摊复杂度接近 O(α(n))α(n) 增长极慢实际可以当成常数。概率分析则关注随机情况下的期望复杂度比如随机快速排序的期望时间是 O(n log n)但最坏仍是 O(n^2)。1.3 课程主线设计策略、分析工具、经典问题算法设计与分析可以理解成三条线交织设计策略、分析工具、经典问题。设计策略包括分治、动态规划、贪心、回溯、分支限界、随机化、近似算法。分析工具包括渐进记号、递归式求解、均摊分析、概率分析、正确性证明。经典问题包括排序、查找、图、字符串、背包、调度、网络流等。下面这张表可以当作复习索引设计策略典型算法适用特征分析重点分治归并排序、快速排序、二分查找子问题独立且规模缩小递归式、合并代价动态规划0-1背包、LCS、LIS最优子结构、重叠子问题状态、转移、边界贪心活动选择、霍夫曼、Prim、Kruskal贪心选择性质、最优子结构交换论证回溯N皇后、子集和、排列解空间树、约束剪枝状态空间大小分支限界0-1背包、TSP求最优解、限界剪枝搜索顺序、界限函数随机化随机快排、随机化选择避免最坏输入期望复杂度近似顶点覆盖、TSP近似NP难问题求较优解近似比这张表建议自己默写一遍。考试时看到题目先判断它属于哪一类再想对应工具。比如“每个物品只能选一次求最大价值”基本是 0-1 背包“区间不重叠最多选几个”是活动选择“从源点到所有点最短路且边权非负”是 Dijkstra。分类清楚了思路就不会乱。注意不要一上来就套模板。先确认问题约束比如边权有没有负数、图是否连通、物品能否分割、数据规模多大。约束变了算法就要换。2. 复杂度分析知识点总结与常见坑2.1 渐进记号与函数阶渐进记号是算法分析的语言。O 是上界Ω 是下界Θ 是上下界同阶。小 o 表示严格上界小 ω 表示严格下界。考试里常考“以下哪个式子正确”比如 n^2 3n 2 O(n^2) 正确n^2 O(n) 错误。注意 O 只要求存在常数 c 和 n0使得 n ≥ n0 时成立。所以 1000000n O(n)常数不改变阶。函数阶比较可以用极限法lim f(n)/g(n)。如果极限是常数则 f Θ(g)如果是 0则 f O(g) 且不是 Θ如果是无穷反过来。比如 n log n 和 n^1.5前者增长更慢。考试里常把 log n、n、n log n、n^2 放在一起比较画图记最稳。一个常见坑是混淆“最好、最坏、平均”。插入排序最好 O(n)最坏 O(n^2)平均 O(n^2)。快速排序最好和平均 O(n log n)最坏 O(n^2)。堆排序最好、最坏、平均都是 O(n log n)。如果题目只写“快速排序的时间复杂度”严格说应该分情况但很多教材默认平均 O(n log n)。2.2 递归式求解代入法、递归树、主定理递归式求解是算法分析的重点。三种常用方法代入法、递归树、主定理。代入法是猜一个界再用数学归纳法证明。比如 T(n) 2T(n/2) n猜 T(n) O(n log n)代入后验证。递归树是把每层代价画出来求和。主定理适合 T(n) aT(n/b) f(n) 这种形式。主定理三种情况如果 f(n) O(n^(log_b a - ε))则 T(n) Θ(n^(log_b a))。如果 f(n) Θ(n^(log_b a))则 T(n) Θ(n^(log_b a) log n)。如果 f(n) Ω(n^(log_b a ε))且满足正则条件则 T(n) Θ(f(n))。举个常考例子T(n) 2T(n/2) n。a2b2log_b a 1f(n)n Θ(n^1)属于第二种所以 T(n)Θ(n log n)。这就是归并排序。T(n)T(n/2)1a1b2log_b a0f(n)1Θ(1)属于第二种所以 T(n)Θ(log n)。这是二分查找。递归树适合主定理不适用的情况比如 T(n)T(n-1)n。展开后是 n(n-1)...1O(n^2)。如果遇到 T(n)2T(n-1)1展开是 2^n 量级。2.3 均摊分析与概率分析均摊分析不关注单次最坏而看一系列操作的平均代价。动态数组插入是典型例子容量满了就扩容单次扩容 O(n)但每两次扩容之间会插入很多次把扩容代价摊到每次插入上就是 O(1)。并查集的路径压缩也是均摊思想查询次数越多树越扁。概率分析适合随机算法。随机快速排序每次随机选主元不会被人为构造的最坏输入卡住。期望复杂度 O(n log n)。随机化选择算法求第 k 小期望 O(n)。这里要注意“期望”不是“一定”理论上仍有极小概率很差但实际很稳。均摊和平均容易混。平均复杂度通常对输入分布做假设均摊复杂度不假设输入分布而是对操作序列做整体分析。考试答题时写清楚“均摊”还是“平均”别混用。2.4 常见复杂度速查表算法/操作最好平均最坏空间冒泡排序O(n)O(n^2)O(n^2)O(1)插入排序O(n)O(n^2)O(n^2)O(1)选择排序O(n^2)O(n^2)O(n^2)O(1)归并排序O(n log n)O(n log n)O(n log n)O(n)快速排序O(n log n)O(n log n)O(n^2)O(log n)堆排序O(n log n)O(n log n)O(n log n)O(1)二分查找O(1)O(log n)O(log n)O(1)BFS/DFSO(VE)O(VE)O(VE)O(V)Dijkstra 堆优化O((VE)log V)同左同左O(VE)KMPO(nm)O(nm)O(nm)O(m)这张表不是让你死背而是用来快速对照。比如题目数据规模 n ≤ 10^5O(n^2) 基本会超时要考虑 O(n log n) 或 O(n)。n ≤ 20 可以暴力回溯。n ≤ 10^6 通常要 O(n) 或 O(n log n) 且常数小。3. 经典算法设计策略拆解3.1 分治归并排序、快速排序、二分查找分治三步分解、解决、合并。子问题相互独立规模缩小到一定程度直接求解。归并排序是最标准的分治把数组分成两半递归排序再合并两个有序数组。合并操作是 O(n)递归深度 O(log n)所以总复杂度 O(n log n)。归并排序稳定但需要额外 O(n) 空间。快速排序也是分治但重点是划分。选一个主元把小于等于它的放左边大于它的放右边再递归两边。快排平均 O(n log n)最坏 O(n^2)。随机选主元或三数取中可以降低最坏概率。快排原地排序空间 O(log n) 递归栈但不稳定。二分查找是分治的退化版每次只解决一个子问题。前提是数组有序。代码简单但边界容易错。我习惯用左闭右闭写法int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }mid left (right - left) / 2是为了防止 leftright 溢出。边界更新必须让区间缩小否则死循环。找左边界、右边界时mid的计算和更新方向要相应调整。3.2 动态规划状态、转移、边界、优化动态规划解决多阶段决策问题核心是状态定义、转移方程、初始化和遍历顺序。能用 DP 的问题通常有两个性质最优子结构和重叠子问题。最优子结构指全局最优包含子问题最优重叠子问题指递归会重复计算所以用表存起来。以 0-1 背包为例物品重量 w[i]价值 v[i]容量 C。定义 dp[i][j] 为前 i 个物品在容量 j 下的最大价值。转移不选第 i 个物品dp[i][j]dp[i-1][j]选则 dp[i][j]dp[i-1][j-w[i]]v[i]前提 j≥w[i]。取两者最大。空间优化成一维后容量要倒序遍历保证每个物品只用一次。int knapsack(int C, vectorint w, vectorint v) { vectorint dp(C 1, 0); for (int i 0; i w.size(); i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[C]; }倒序是重点。如果正序就变成完全背包因为同一个物品可能被重复选。另一个高频题是最长公共子序列 LCSdp[i][j] 表示 A 前 i 个和 B 前 j 个的 LCS 长度。相等时 dp[i][j]dp[i-1][j-1]1否则取 dp[i-1][j] 和 dp[i][j-1] 的最大值。DP 常见坑状态定义不清晰、边界没初始化、遍历顺序错、空间优化后更新方向错。做题时先写二维朴素版再改一维。不要一上来就写滚动数组错了很难查。3.3 贪心活动选择、霍夫曼、最小生成树贪心算法每一步选当前看起来最好的不回头。难点是证明贪心选择性质。活动选择问题每个活动有开始和结束时间选最多不冲突活动。按结束时间升序排序依次选结束早且与已选不冲突的。为什么按结束时间因为结束越早留给后面的时间越多。这是交换论证的典型。霍夫曼编码也是贪心每次取两个频率最小的节点合并直到只剩一个根。得到的编码是最优前缀码。Prim 和 Kruskal 求最小生成树也是贪心。Prim 从一个点开始每次加一条连接已选集合和未选集合的最小边Kruskal 按边权排序用并查集判断是否成环。贪心的坑是“看起来对”但实际不对。比如 0-1 背包不能按单位价值贪心因为物品不可分割。分数背包可以按单位价值贪心。判断标准是问题是否满足贪心选择性质。考试如果要求证明一定要写交换论证或归纳。3.4 回溯与分支限界N皇后、0-1背包回溯法本质是带剪枝的 DFS。解空间是一棵树每个节点代表部分解发现不满足约束就回溯。N 皇后是经典逐行放皇后检查列、主对角线、副对角线是否冲突。可以用三个布尔数组 O(1) 判断。void solve(int row, int n, vectorstring board, vectorbool col, vectorbool diag1, vectorbool diag2) { if (row n) { ans.push_back(board); return; } for (int c 0; c n; c) { int d1 row - c n; int d2 row c; if (col[c] || diag1[d1] || diag2[d2]) continue; board[row][c] Q; col[c] diag1[d1] diag2[d2] true; solve(row 1, n, board, col, diag1, diag2); board[row][c] .; col[c] diag1[d1] diag2[d2] false; } }分支限界在回溯基础上加入界限函数优先搜索更有希望的分支。0-1 背包的分支限界可以用“当前价值 剩余物品按单位价值装满的上界”来剪枝。TSP 的分支限界用当前路径长度加最小出边下界。分支限界适合求最优解但实现复杂度高考试更常考思想。3.5 随机化与元启发式模拟退火、粒子群随机化算法用随机数做决策。随机快排、随机化选择、Miller-Rabin 素性测试都是典型。元启发式算法如模拟退火、粒子群、蚁群、遗传算法适合传统精确算法难以处理的优化问题。模拟退火模拟金属退火以一定概率接受较差解避免陷入局部最优。粒子群模拟鸟群觅食每个粒子根据个体最优和全局最优调整速度和位置。这些算法在工程里常出现在参数调优、路径规划、调度、神经网络超参搜索中。它们不保证全局最优但能在可接受时间内给出较优解。学算法设计与分析时重点是理解它们的复杂度、参数影响和适用边界。比如模拟退火的初始温度、降温系数、终止条件都会影响结果调参经验比公式更重要。4. 图算法与字符串算法高频考点4.1 图的表示、BFS/DFS、拓扑排序图有两种主流表示邻接矩阵和邻接表。邻接矩阵适合稠密图查询边 O(1)空间 O(V^2)。邻接表适合稀疏图空间 O(VE)遍历邻居方便。BFS 用队列按层扩展能求无权图最短路。DFS 用栈或递归适合连通性、环检测、拓扑排序。拓扑排序针对有向无环图。Kahn 算法统计入度入度为 0 的入队出队时把邻居入度减 1减到 0 再入队。如果最终输出节点数小于总节点数说明有环。DFS 也可以做拓扑排序后序遍历逆序就是拓扑序。注意BFS 求最短路只适用于边权相同或无权图。边权不同要用 Dijkstra 或 Bellman-Ford。4.2 最小生成树Prim、Kruskal最小生成树在无向连通带权图中找一棵总权最小的生成树。Prim 适合稠密图复杂度 O(V^2) 或堆优化 O(E log V)。Kruskal 适合稀疏图按边权排序用并查集加边复杂度 O(E log E)。Kruskal 的并查集实现int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; parent[ra] rb; return true; }考试常考“Prim 和 Kruskal 哪个更适合什么图”。稠密图边多Kruskal 排序成本高Prim 更合适稀疏图边少Kruskal 更简单。两者都基于贪心正确性用切分定理证明。4.3 最短路径Dijkstra、Bellman-Ford、FloydDijkstra 求非负权图单源最短路。朴素版每次找未访问最小距离点复杂度 O(V^2)堆优化 O((VE)log V)。不能处理负权边因为贪心选择不再成立。Bellman-Ford 可以处理负权边做 V-1 轮松弛复杂度 O(VE)还能检测负环。Floyd 求所有点对最短路三重循环 O(V^3)适合小规模稠密图。Dijkstra 堆优化模板vectorint dijkstra(int n, vectorvectorpairint,int g, int s) { vectorint dist(n, INT_MAX); priority_queuepairint,int, vectorpairint,int, greater pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }if (d ! dist[u]) continue;是懒惰删除避免处理过期堆元素。负权图换 Bellman-Ford 或 SPFA但 SPFA 最坏可能退化竞赛中要小心。4.4 最大流与二分图匹配匈牙利算法最大流解决网络流问题Ford-Fulkerson、Edmonds-Karp、Dinic 是常见算法。Edmonds-Karp 用 BFS 找增广路复杂度 O(VE^2)。Dinic 加分层图和当前弧优化效率更高。二分图匹配可以用匈牙利算法核心是不断找增广路。时间复杂度 O(VE)。匈牙利算法适合任务分配、配对问题。代码不长但理解“增广路”是关键。每次尝试给左部节点找匹配如果右部节点已匹配就递归尝试让原配换一个。匹配数增加一。4.5 字符串匹配KMP、TrieKMP 解决模式串在主串中的匹配复杂度 O(nm)。核心是 next 数组记录模式串前缀和后缀的最长公共长度。匹配失败时模式串指针回退到 next[j-1]而不是从头开始。vectorint buildNext(string p) { vectorint nxt(p.size(), 0); int j 0; for (int i 1; i p.size(); i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] j; } return nxt; }Trie 适合前缀查询、词典匹配、自动补全。每个节点有若干子节点和一个结束标记。插入和查询都是 O(L)L 是字符串长度。空间换时间字符集大时可以用哈希表存子节点。5. 排序算法与数据结构配合5.1 比较排序冒泡、插入、归并、快排、堆排序冒泡排序相邻比较交换每轮把最大元素冒到最后。最好 O(n)已有序且加标志平均和最坏 O(n^2)稳定。插入排序像整理扑克牌左边已有序右边元素插入合适位置。小规模或基本有序时很快。选择排序每轮选最小放前面交换次数少但不稳定复杂度固定 O(n^2)。归并排序稳定适合链表排序和外部排序。快速排序平均最快原地排序但最坏 O(n^2)不稳定。堆排序利用堆结构建堆 O(n)每次取堆顶再调整 O(log n)总 O(n log n)原地但不稳定。实际工程中很多标准库排序用混合策略比如内省排序快排递归太深时切堆排序小数组用插入排序。5.2 非比较排序计数、基数、桶比较排序下界是 O(n log n)非比较排序可以突破但有条件。计数排序适合范围小的整数统计每个值出现次数再前缀和确定位置复杂度 O(nk)稳定。基数排序按位从低到高排序每位用计数排序复杂度 O(d(nk))适合整数和定长字符串。桶排序把数据分到若干桶桶内再排序平均 O(n)最坏 O(n^2)。非比较排序的坑是数据范围。如果整数范围极大计数排序空间爆炸。基数排序的位数和基数要权衡。桶排序依赖数据分布均匀否则退化成普通排序。5.3 堆、并查集、树状数组与线段树堆是优先队列的基础插入和删除堆顶 O(log n)取堆顶 O(1)。大顶堆用于求最大值小顶堆用于求最小值。堆排序、Dijkstra、霍夫曼编码都用堆。并查集管理不相交集合支持查找和合并。路径压缩加按秩合并后接近常数。用于 Kruskal、连通性判断、朋友圈问题。树状数组支持单点更新和前缀查询复杂度 O(log n)。线段树支持区间查询和区间更新功能更强但代码更长。考试常考树状数组求逆序对、线段树求区间最值。选择时看操作类型只查前缀用树状数组任意区间用线段树。5.4 排序稳定性与选择建议排序算法稳定性原地适用场景冒泡稳定是教学、小规模插入稳定是小规模、基本有序选择不稳定是交换次数少归并稳定否链表、外部排序快速不稳定是通用内存排序堆不稳定是只需前 k 大、优先队列计数稳定否小范围整数基数稳定否整数、定长字符串稳定性指相等元素排序后相对顺序不变。多关键字排序时先按次要关键字排再按主要关键字稳定排序。比如先按分数排再按姓名稳定排序就能得到姓名有序且分数有序的结果。6. 期末编程题与刷题策略6.1 高频题型清单期末编程题通常集中在几个方向分治求最大子段和、归并排序求逆序对、二分查找边界、动态规划背包和 LCS、贪心活动选择、图的最短路和最小生成树、拓扑排序、KMP、并查集。复习时不要只背代码要能根据输入规模选算法。题型常用算法复杂度目标最大子段和分治或 DPO(n log n) 或 O(n)逆序对归并或树状数组O(n log n)背包DPO(nC)最长公共子序列DPO(nm)活动选择贪心O(n log n)单源最短路DijkstraO((VE)log V)最小生成树Prim/KruskalO(E log V)字符串匹配KMPO(nm)连通块DFS/并查集O(VE)如果题目要求输出方案DP 要记录选择路径。如果只要求数值可以滚动数组。看到“最多”“最少”“最大”“最小”先想优化问题再看是否满足 DP 或贪心。6.2 代码模板与调试技巧考试写代码先写输入输出和数据结构再写核心逻辑。模板要精简避免背太长。比如 Dijkstra 记堆优化框架Kruskal 记排序加并查集DP 记二维转一维。调试时先用手算小数据再打印中间状态。常见调试手段边界数据n0、n1、全部相同、已排序、逆序。极端数据最大规模、最小规模、溢出边界。对拍写一个暴力算法随机生成小数据对比结果。打印状态DP 表、dist 数组、并查集父节点。注意C 中int溢出很常见。最短路累加、DP 价值累加可能超过 2^31-1要用long long。memset只能按字节初始化不能直接把数组设成 1e9。6.3 时间分配与应试策略期末编程题一般 2 到 3 小时。建议先花 10 分钟通读题目标记难度和分值。先做有把握的题拿稳基础分。每道题先写暴力思路再优化。如果卡住超过 20 分钟先跳过去做下一题。最后留 15 分钟检查边界和输入输出格式。写代码时先写注释框架输入、初始化、核心循环、输出。不要一边想一边写容易乱。复杂度估算写在草稿纸上如果超时再换算法。提交前测三个样例题目样例、边界样例、随机小样例。6.4 常见错误排查表现象可能原因排查方法答案偏小边界没初始化、漏状态检查 dp[0]、dist[s]答案偏大重复计算、没剪枝打印中间状态死循环二分边界不缩小、DFS 没标记检查更新方向、visited超时复杂度过高、常数大算数据规模、换算法段错误数组越界、递归太深开大数组、改迭代输出格式错多空格、少换行对照题目要求负权最短路错用了 Dijkstra换 Bellman-Ford背包重复选一维正序遍历改倒序这张表我考试前会看一遍很多低级错误都能避免。7. 算法分析在工程算法里的影子7.1 机器学习与信号处理中的算法取舍学算法设计与分析不只是为了考试。机器学习里的很多算法都能追溯到基础思想。KNN 分类本质是查找最近邻可以用 KD 树优化。K-means 是迭代贪心DBSCAN 基于密度和邻域查询。Sobel 边缘检测是卷积操作复杂度与图像大小成线性关系。PID 控制是反馈调节增量式 PID 在嵌入式里很常见。这些工程算法的分析方式和基础算法一致看时间复杂度、空间复杂度、参数敏感性和收敛性。比如粒子群算法参数多早熟收敛是常见问题模拟退火降温太快容易局部最优太慢又耗时。深度模型训练里的剪枝算法本质是在搜索空间里做取舍和分支限界、贪心有相通之处。7.2 从理论复杂度到真实性能理论复杂度低不代表实际一定快。缓存命中、内存布局、并行度、常数因子都会影响。比如链表归并排序理论 O(n log n)但数组快排往往更快因为数组连续内存缓存友好。Dijkstra 堆优化理论好但小图朴素版可能更快。工程里选算法先看数据规模再看数据特征最后看实现成本。n 很小暴力可能最省事。n 很大且要求严格才上复杂算法。算法设计与分析教的是判断力不是让你所有场景都写最复杂版本。7.3 高级算法与交叉方向高级算法分析与设计会涉及近似算法、在线算法、随机算法、并行算法、量子算法等。比如最大割的近似算法、在线缓存淘汰、MapReduce 算法。计算机视觉、密码学、编译原理里也有大量算法。祖冲之密码算法是分组密码设计卷积码 BCJR 译码是动态规划思想Vue3 diff 算法是树比较和最长递增子序列。学基础算法时把这些当成应用场景理解会更牢。8. 常见问题与排查技巧实录8.1 常见问题速查表问题原因解决不知道用哪种算法没抓问题特征看约束、目标、数据规模DP 状态想不出没定义阶段先写递归暴力再加记忆化贪心不敢用不会证明尝试交换论证、举反例图论建图混乱边和点关系不清画小图、明确有向无向二分总写错区间定义不统一固定左闭右闭或左闭右开递归爆栈深度太大改迭代、加剪枝并查集慢没路径压缩加 find 递归压缩浮点误差直接比较用 eps 或转整数8.2 调试与验证方法调试算法题先保证小数据正确。手算一个 n3 或 n4 的样例跟踪变量。然后写暴力对拍。对拍脚本可以随机生成输入运行两个程序比较输出。如果结果不同缩小数据规模打印中间状态。很多错误在 n1、n0、全相同元素时暴露。验证贪心可以尝试找反例。验证 DP 可以检查状态是否覆盖所有选择。验证图算法可以检查连通性、负权、重边、自环。验证字符串算法可以检查空串、单字符、无匹配、全匹配。8.3 复习节奏与个人心得我自己的复习节奏是三轮。第一轮按章节过知识点每个算法手写一遍伪代码不看书。第二轮刷题按专题刷每个专题 5 到 10 题重点总结错题。第三轮模拟考试限时做期末编程题训练时间分配。错题本不用抄题只记“错因 正确思路 关键代码片段”。算法设计与分析这门课最怕的是只背模板。模板能帮你快速起步但遇到变形题就失效。真正有用的是看到问题先分类再想策略再估复杂度最后写代码。平时练习时多问一句“为什么这个算法正确”比多刷十道同类题更有价值。最后分享一个我常用的复习技巧把每个经典算法讲给一个完全不懂的人听如果能讲到对方明白“它解决什么问题、为什么快、什么时候不能用”说明你真的掌握了。遇到讲不通的地方就是知识漏洞回去补那一块。