1. 复习前的整体思路算法分析复习这四个字听起来像是考试前临时抱佛脚但真正完整走过一两轮之后会发现它更像是一次对思维方式的重新校准。这门内容研究的不是怎么写出一段能跑的代码而是这段代码在输入规模不断变大之后会变成什么样子。它要回答的是增长速度、资源上界、最坏情况这些听起来抽象、实际上每天都在用的东西。不管手头拿的是哪一本数据结构与算法分析的教材也不管描述语言用的是 C 还是别的核心骨架其实是同一套用渐进记号刻画代价用递归式描述分治用状态定义刻画规划用交换论证支撑贪心。骨架吃透了题目怎么变形都不至于慌。不少人复习到一半会陷入一种状态单个知识点都懂一拿到综合题就不知道从哪儿下手。问题往往不在知识点上而在没有把分析和设计两条线接起来。分析是从代码倒推代价设计是从代价要求倒推结构。复习时把这两条线来回走几遍比单纯刷题有用得多。1.1 算法分析复习到底在复习什么拆开看这门内容大概有三层。第一层是代价度量。给定一段代码或者一个递推过程你要能在几分钟内给出它的渐进上界并且说清楚这个上界是在什么输入分布下成立的。这一层靠的是熟练度属于基本功。第二层是算法设计范式。分治、动态规划、贪心、回溯、分支限界每一种范式都有它适用的结构特征。看到最优子结构加重叠子问题就该想到动态规划看到局部最优能推出全局最优就该考虑贪心。这一层靠的是模式识别属于经验积累。第三层是正确性论证。为什么贪心是安全的为什么主定理的某个情况在这里失效为什么这个下界是紧的。这一层最容易被跳过但它恰恰是拉开差距的地方因为前两层靠背和练能补上第三层只能靠真正理解。三层之间的关系是层层递进的。代价度量不过关范式选得再对也写不出能过的方案范式识别不准正确性论证根本无从谈起。1.2 时间不够时的取舍策略如果距离考试或者面试只剩一两周我建议按下面的优先级排。必拿分渐进记号的定义与判断、常见结构的复杂度速算、主定理三种情况的套用、常见排序与查找的复杂度对照。这些是每次都会出现的内容投入产出比最高。重点攻动态规划的状态设计、分治算法的时间分析、图算法的手工模拟过程。这三块是区分度的主要来源。有空再看网络流的建模细节、NP 完全性的归约证明、均摊分析里的势能法。这些属于加分项理解框架即可不必强求每个都能独立推导。提示取舍不等于放弃。某些看起来冷门的内容恰恰是笔试里用来区分层次的那一两道题框架性的理解至少要保留。1.3 我用的复习节奏和材料组合我的做法是三轮走。第一轮用一到两天把教材里所有代码和递推式过一遍只做一件事给每个算法手写一遍复杂度分析不看书。第二轮花三到四天集中做题重点是那些需要写出完整推导过程的题目逼自己把每一步理由写清楚。第三轮只剩一天闭卷默写核心表格和主定理的适用条件。材料方面一本讲清原理的教材加一份习题集就够了不需要铺开太多。教材用来建立框架习题集用来暴露漏洞。真正有用的往往不是新书而是同一本书的第二遍、第三遍因为第一遍你会漏掉大量细节。2. 渐进复杂度分析绕不过去的地基复杂度分析是整门内容的地基地基不牢后面全是空中楼阁。很多人觉得自己会算复杂度但一旦遇到嵌套里带对数、循环变量非线性变化、或者递归式里带根号的情况就开始凭感觉猜。这个部分我建议老老实实按定义推几遍把直觉建立在严格定义之上。2.1 五个渐进记号的区别和实际使用场合教材里通常会给五个记号但真正需要区分清楚的主要是三个上界、下界、紧界。它们的关系可以这样理解。记号含义类比常见使用场合O渐进上界预算上限描述最坏情况下不会超过多少Ω渐进下界成本下限证明某问题至少需要多少代价Θ渐进紧界上下都卡住上下界相同时的标准写法o严格上界永远追不上用于区分同阶但非紧的情况ω严格下界永远够不着与 o 对称最容易出错的是 O 和 Θ 的混用。比如归并排序说它的运行时间是 O(n²) 在数学上并没有错因为 n log n 确实不超过 n² 的某个常数倍。但这个说法毫无信息量。日常表达里我们默认用 O 表示最紧的上界这是行业惯例但考试里如果要求严格就必须写 Θ。判断两个函数谁是谁的界最稳妥的方法是取极限lim(n→∞) f(n)/g(n)结果为零说明 f 的量级严格小于 g结果为常数说明两者同阶结果为无穷说明 f 更大。这个方法比死记谁长得快可靠得多尤其面对对数幂、指数底数混合的情况。2.2 循环与嵌套结构的复杂度速算单层循环看循环变量的变化幅度嵌套循环不能简单地乘起来关键看内层和外层有没有依赖关系。看一个常见的陷阱for (int i 1; i n; i * 2) { for (int j 0; j i; j) { do_something(); } }外层执行次数是 log n 级别内层执行次数依次是 1、2、4、8……呈等比增长。总次数是 124...n等比数列求和后是 2n-1所以整体是 Θ(n)不是很多人第一反应写的 Θ(n log n)。再看一个for (int i 0; i n; i) { for (int j i; j n; j) { do_something(); } }内层次数依次是 n、n-1、n-2……求和是 n(n1)/2所以是 Θ(n²)。这个大家都会但要注意它和上一个例子的区别这里内层是线性递减求和是二次上一个例子内层是等比增长求和是线性。我整理了一个速查表遇到循环结构时先对照分类结构特征总代价典型例子外层线性内层线性Θ(n²)冒泡排序、简单选择外层对数内层线性Θ(n)等比增长的嵌套外层线性内层对数Θ(n log n)每次二分查找的遍历外层对数内层对数Θ(log² n)双重倍增结构外层线性内层常数Θ(n)单层扫描注意看到嵌套千万不要条件反射地相乘。先看循环变量的更新方式再看内层范围是否依赖外层变量最后决定是乘积、求和还是等比求和。2.3 递归式求解代入法、递归树、主定理递归式的求解有三大手段各有适用场景。代入法适合验证已经猜到的结论。做法是先猜一个形式比如猜 T(n) O(n log n)然后用数学归纳法代进去验证。关键在于放缩的技巧比如把 n/2 放大到 n 之后还能不能把常数项吸收掉。这个方法灵活但不适合从零开始找答案。递归树适合建立直觉。把递归过程画成一棵树每一层写清楚该层的工作量然后把所有层加起来。以归并排序为例T(n) 2T(n/2) cn第 0 层代价 cn第 1 层两个节点共 2 × c(n/2) cn第 2 层 cn……一直到叶子层节点数变成 n每个节点常数代价总计 cn。树高是 log n所以总数是 cn log n。主定理是最省事的工具但它的适用条件必须记住。对于形如T(n) aT(n/b) f(n)的递归式比较 f(n) 和 n 的 log_b(a) 次方这两个量情况条件结论情况一f(n) 多项式小于 n^(log_b a)T(n) Θ(n^(log_b a))情况二两者同阶差一个对数因子T(n) Θ(n^(log_b a) log n)情况三f(n) 多项式大于且满足正则条件T(n) Θ(f(n))所谓多项式小于是指存在某个正的常数 ε 使得 f(n) O(n^(log_b a - ε))。如果只是比它小一点点比如差了个 log n 因子那就落在情况二不能按情况一处理。这一点坑过很多人。2.4 均摊分析与摊还代价均摊分析处理的是偶尔很贵、大部分时候很便宜的操作序列。经典例子是动态数组的扩容单次插入大部分是 O(1)但扩容那一次是 O(n)。三种方法里聚合分析最直观把 n 次操作的总代价算出来除以 n。还是动态数组从空数组开始连续插入 n 个元素所有扩容的总代价是 124...n 2n加上每次插入本身的一次赋值得 n总计小于 3n所以每次操作均摊是 O(1)。记账法是给每个便宜操作多收一点虚拟币存起来贵操作时花掉。势能法是定义一个势能函数用势能的变化量来平衡代价。这两者本质相通只是视角不同。势能法在处理一些结构复杂的摊还分析时更好用比如伸展树的均摊分析就常用它。实操心得均摊代价描述的是操作序列的平均表现不是单次操作的上界。如果题目问的是某一次操作的最坏代价那就老老实实回答 O(n)不要拿均摊值去答。3. 分治与递归把大问题拆碎的通用套路分治的思想朴素到有点不像技巧把问题拆小解决小问题再合并结果。但真正难的是怎么拆和怎么合并以及拆完之后代价怎么算。复习这一块重点不在于记住具体的算法而在于掌握拆解与合并的通用分析框架。3.1 分治三步骤的代码落点分治的三步骤——分解、解决、合并——在代码里对应得非常清楚。以归并排序为例分解就是取中点解决就是递归排序左右两半合并就是双指针归并。void merge_sort(int *a, int *tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(a, tmp, left, mid); /* 分解并解决左半 */ merge_sort(a, tmp, mid 1, right); /* 分解并解决右半 */ /* 合并双指针写入 tmp 再拷回 */ int i left, j mid 1, k left; while (i mid j right) tmp[k] (a[i] a[j]) ? a[i] : a[j]; while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (int t left; t right; t) a[t] tmp[t]; }拆解的关键在于子问题的规模要按比例缩小而不是按常数缩小。如果每次只把规模减一递归深度就是线性的代价会退化成 O(n²)。这解释了为什么快排和归并都要取中点而不是从两边各砍掉一个元素。合并的代价决定了整体复杂度里那个额外项。归并的合并是 O(n)二分查找的合并是 O(1)快速排序干脆不需要合并。所以同样是分治三者的复杂度差别很大。3.2 主定理的三种情况与失效场景主定理好用但它的边界经常被忽略。下面这几种情况主定理是处理不了的。第一种递归式不是标准形式。比如 T(n) T(n-1) n子问题规模是减一而不是按比例缩小a 和 b 都取不出来。这类要用递归树或者展开法答案是 Θ(n²)。第二种子问题规模不同。比如 T(n) T(n/3) T(2n/3) n左右两半规模不一样没法直接套。这种要用递归树把每层代价加起来树的深度由最长路径决定这里是 log 的底数 3/2每层代价是 n所以总代价是 Θ(n log n)。第三种比较结果落在情况一和情况二的夹缝里。比如 T(n) 2T(n/2) n log n这里 n^(log_2 2) nf(n) n log n比 n 大但不是多项式级别的大只差一个对数因子所以主定理的三种情况都套不上。答案是 Θ(n log² n)用递归树能推出来。第四种不满足正则条件。主定理的情况三要求 f(n) 满足 af(n/b) ≤ cf(n) 对某个 c 1 成立。有些函数虽然量级够大但震荡得厉害不满足这个条件情况三就用不了。提示拿到一个递归式先别急着套主定理花十秒确认三件事——是不是标准形式、子问题规模是否一致、f(n) 和 n^(log_b a) 之间是不是多项式级别的差距。3.3 两个经典题目的完整复盘最大子数组问题是个很好的分治练习。给定一个数组找出和最大的连续子数组。分治的做法是把数组从中点切开答案要么完全在左半要么完全在右半要么跨越中点。跨越中点的情况是重点从中点向左右分别扫描记录左半以中点为结尾的最大和以及右半以中点开始的最大和两者相加就是跨越中点的最大和。这一步是 O(n)。int max_crossing(int *a, int l, int m, int r) { int sum 0, left_max INT_MIN; for (int i m; i l; i--) { sum a[i]; if (sum left_max) left_max sum; } sum 0; int right_max INT_MIN; for (int j m 1; j r; j) { sum a[j]; if (sum right_max) right_max sum; } return left_max right_max; }整体递归式是 T(n) 2T(n/2) Θ(n)套主定理得到 Θ(n log n)。这个题的另一个解法是动态规划能做到 Θ(n)但那是另一条思路复习时两条路都走一遍收获更大。二分查找的变体是另一个值得反复练的题目。标准二分查找只是找某个元素是否存在但实际题目里更多是找边界第一个大于等于目标的位置、最后一个小于目标的位置。这类题目的分治结构没变复杂度仍然是 Θ(log n)但循环的边界条件和返回值处理非常容易出错。我个人的经验是把区间定义成左闭右开并且全程保持一致错误率能降一大截。4. 动态规划状态定义才是真正的难点动态规划这部分初学者容易把注意力全放在转移方程上实际上方程往往是状态定义好之后自然就出来的东西。真正难的是想清楚状态该记什么和状态之间怎么转移这两件事。复习的重点应该放在状态设计的思路上而不是背题。4.1 状态定义是整个 DP 的灵魂一个好的状态定义通常满足两个条件能覆盖所有需要区分的情况并且维度不能爆炸。以最长递增子序列为例。一个很自然的想法是定义 dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。为什么一定要以第 i 个结尾因为只有固定了结尾才能判断下一个元素能不能接上去。如果不固定结尾状态就没法转移。int length_of_lis(int *a, int n) { int *dp malloc(n * sizeof(int)); int ans 1; for (int i 0; i n; i) { dp[i] 1; for (int j 0; j i; j) if (a[j] a[i] dp[j] 1 dp[i]) dp[i] dp[j] 1; if (dp[i] ans) ans dp[i]; } return ans; }这个状态定义带来的代价是 O(n²)因为转移时要遍历所有前驱。如果想优化到 O(n log n)就需要换一种状态定义方式用长度为 k 的递增子序列的最小结尾来刻画配合二分查找。同一道题状态定义一变复杂度就变了这就是状态设计的威力。再比如背包问题。0-1 背包的状态是 dp[i][j] 表示前 i 件物品、容量 j 下的最大价值。为什么不定义成 dp[i] 表示前 i 件物品能达到的最大价值因为容量是约束条件不记容量就无法判断还能不能放下一件物品。这类决策加约束的问题状态里必须同时体现两者。4.2 从记忆化搜索到递推的转换很多人觉得递推难写是因为一上来就想套循环。更稳的路子是先写记忆化搜索也就是带备忘录的递归跑通之后再把递归改成递推。写记忆化搜索的好处是你只需要关心当前状态从哪些前驱状态转移过来不需要操心循环的顺序。等逻辑验证正确了再根据依赖关系确定递推方向。以 0-1 背包为例记忆化形式是这样的int memo[N][W]; /* 初始化为 -1 */ int dp(int i, int j) { if (i 0 || j 0) return 0; if (memo[i][j] ! -1) return memo[i][j]; int res dp(i - 1, j); /* 不选第 i 件 */ if (j weight[i]) res max(res, dp(i - 1, j - weight[i]) value[i]); return memo[i][j] res; }改成递推的时候观察依赖dp(i, j) 依赖 dp(i-1, ...)所以外层循环按 i 从小到大即可内层按 j 从小到大也行因为依赖的是上一行的数据。实操心得写不出递推式的时候先写记忆化搜索。它的正确性容易保证而且能直接暴露出状态依赖关系改写成递推只是机械操作。4.3 空间压缩与滚动数组递推写出来之后可以进一步做空间优化。0-1 背包的二维数组可以压成一维关键是内层循环要逆序。for (int i 0; i n; i) for (int j W; j weight[i]; j--) dp[j] max(dp[j], dp[j - weight[i]] value[i]);为什么必须逆序因为正序的话dp[j - weight[i]] 可能已经是本轮更新过的值等于同一件物品被放了多次那就变成了完全背包。逆序保证了用的是上一轮的值也就是还没考虑当前物品时的状态。这个细节是考试里非常喜欢考的点。判断该正序还是逆序有个简单的办法看这个物品能不能重复选。能重复选就正序不能就逆序。另外还有一类压缩是用滚动数组在行之间来回切换。当状态只依赖上一行时用两行交替即可省下大量空间。当依赖的跨度更大时滚动数组就不够用了得用其他手段。5. 贪心与图算法容易踩坑的边界贪心和动态规划看起来都很像一步步做决策但区别在于贪心只做一次选择而且不回头。这个特性让贪心写得快、跑得快但也让它更容易出错。图算法则是另一个重灾区因为很多算法的细节条件记不清就会用错。5.1 贪心正确性的证明套路贪心的证明有两条主要路径交换论证和归纳法。交换论证的思路是假设存在一个最优解如果它和贪心选择不一样那么把它改成贪心选择之后解不会变差。以活动选择问题为例按结束时间排序后选第一个结束最早的活动假设最优解选的不是它那么用这个更早结束的活动替换掉最优解里的第一个活动剩下的活动依然可以接上解的数量不变所以贪心选择是安全的。归纳法的思路是证明贪心的每一步都保持了存在一个包含当前选择的最优解这个不变式。哪种情况贪心会失效关键看问题有没有用局部牺牲换全局收益的可能。经典的 0-1 背包就是反例如果按单位价值排序贪心选择遇到一个单位价值高但体积也大的物品选了它之后剩下的空间可能什么都放不下反而不如选两个单位价值略低但体积小的物品。所以 0-1 背包必须用动态规划。分数背包则可以用贪心因为物品可以切分不存在选了就占满的问题。这一对例子几乎是所有教材都会拿来做对比的值得记住。5.2 最短路径与最小生成树的选型图算法的选型其实只需要记一张表但要注意每条的适用条件。算法解决的问题适用条件复杂度Dijkstra单源最短路边权非负O((VE) log V) 堆优化Bellman-Ford单源最短路允许负权可判负环O(VE)Floyd多源最短路允许负权不能有负环O(V³)Prim最小生成树无向连通图O(E log V) 堆优化Kruskal最小生成树无向连通图配合并查集O(E log E)Dijkstra 遇到负权边会出错原因是它基于一个假设已经确定的最短路径不会再被更新。负权边会破坏这个假设。如果图里有负权就必须换成 Bellman-Ford。Prim 和 Kruskal 的取舍主要看图的稠密程度。稠密图用 Prim因为它的复杂度主要跟顶点数相关稀疏图用 Kruskal因为它的复杂度主要跟边数相关。Floyd 的三重循环有个细节很容易写错中间节点的循环必须放在最外层。for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][k] dist[k][j] dist[i][j]) dist[i][j] dist[i][k] dist[k][j];如果把 k 放到内层算出来的结果就错了。原因是这个过程的正确性依赖于允许经过的中间节点集合逐步扩大这个不变式k 必须是最外层才能保证这个性质。注意Floyd 的循环顺序是最高频的出错点之一复习时至少要手写三遍确认无误。5.3 网络流建模的思考路径网络流的算法本身比如 Dinic实现起来不算太难难的是把实际问题建模成网络流。复习这一块重点应该放在建模思路上。建模的核心是回答三个问题什么作为流、什么作为容量、源点和汇点分别是什么。以二分图匹配为例。左边一排是待分配的对象右边一排是被分配的对象每条边代表一个可行的匹配。把源点连向左边所有点容量 1左边连向右边容量 1右边连向汇点容量 1跑最大流就是最大匹配数。这个转换之所以成立是因为容量为 1 保证了每个点只被用到一次。再比如带限制的分配问题某些任务必须分给特定的人某些人有工作量上限。这时把人拆成两个点中间连一条容量为人上限的边用来限制总量。这叫拆点法是网络流建模里最常用的技巧之一。判断一个问题能不能用网络流做有个粗略的经验如果问题里存在分配匹配选择且互斥这类结构而且约束可以用容量表达那大概率可以建模。6. 复习中的常见问题与排查技巧复习到后期真正卡人的往往不是不会而是会但是算错懂但是写错。这一节整理一些高频问题和我自己的排查习惯都是踩过坑之后总结出来的。6.1 复杂度分析算错的几类典型场景第一类把最坏情况和平均情况搞混。快速排序最坏是 O(n²)平均是 O(n log n)。如果题目问的是最坏情况回答平均复杂度就是答非所问。第二类忽略隐藏的对数因子。堆排序每次调整是 O(log n)总共 n 次所以是 O(n log n)。有人会漏掉那个 log直接写成 O(n)。第三类把树的高度算错。完全二叉树的高度是 O(log n)但链状的二叉搜索树高度是 O(n)此时查找退化成 O(n)。这个区别在分析平衡树的时候特别重要。第四类混淆递归深度和总调用次数。递归深度决定了栈空间的开销总调用次数决定了时间开销。二叉树遍历的时间是 O(n)但空间是 O(h)h 是树高两者不能混为一谈。排查的办法很简单每算完一个复杂度反问自己三个问题——最坏输入是什么、每层的工作量是多少、一共有多少层。这三个问题能答清楚答案基本不会错。6.2 题目做不出来时的破局顺序遇到一道题完全没思路我通常按下面的顺序试。看数据范围。n 是 10³、10⁵ 还是 10⁶直接暗示了能接受的复杂度。10³ 通常允许 O(n²)10⁵ 一般要求 O(n log n)10⁶ 就得 O(n) 或 O(n log n) 且常数要小。想暴力解法。先把最朴素的做法写出来哪怕是指数级的。有了暴力解就能看出哪些状态被重复计算了。找重复子问题。如果有大量重复就往记忆化或者 DP 上靠。如果没有重复看看能不能分治或者贪心。看有没有单调性。如果决策随着某个变量的增大而呈现单调变化二分或者双指针可能适用。试构造反例。想到一个贪心策略之后花一分钟试着构造反例构造不出来再往正确性证明上走。这个顺序的价值在于它从已知出发每一步都建立在上一部的信息之上而不是凭空猜。6.3 笔试面试中的表达与书写习惯最后说点考试技巧。算法分析类题目很多时候过程比答案更重要。书写时我会遵守几条不成文的规矩。结论先写推导后附阅卷的人一眼就能看到结果。放缩的每一步都标出依据比如因为 k n所以……。递归式先写出来再求解不要跳过建模直接给答案因为建模本身就占分。如果是面试口头表达时尽量说清楚三件事这个算法解决了什么问题、它的时间空间开销是什么量级、什么情况下它会退化。第三点特别容易加分因为它说明你不是只会背而是真的理解了边界。实操心得复习到后期与其继续刷新题不如把之前做错的题重做一遍尤其是那种看答案秒懂、自己做想不到的题。这类题暴露的是思维盲区重复暴露才能真正补上。我自己的体会是算法分析这门东西的复习效果不在做题数量上而在每一道题都能说清楚为什么上。能说清楚为什么说明框架已经建起来了说不出为什么做再多题也只是记住了一些孤立的结论。这个方法用了几轮以后我再遇到没见过的题型也不会完全空白因为至少知道该从哪个角度切入剩下的是时间问题。