算法设计与分析这门课在计算机专业的培养方案里属于那种平时不听课、期末火葬场的硬骨头。它跟数据结构不一样数据结构还能靠刷题练手感这门课要求你在两小时内既能把一个递推式的时间复杂度算得清清楚楚又能现场手推矩阵连乘的填表过程还得在草稿纸上默写出完整的归并排序或者KMP的next数组。所以考前突击这件事对算法设计与分析来说策略远比蛮力重要。我把自己和身边同学在48小时内从几乎零基础冲到及格线以上的整套打法梳理了出来覆盖复杂度分析、分治、动态规划、贪心、图算法、回溯与分支限界、NP完全性这几大板块同时把高频编程题的手写模板和临场取舍技巧一起写清楚。无论你是前期完全没听、现在只剩两个通宵的极限选手还是想临门补漏多抢十几分的稳过党下面这些内容都能直接拿来用。1. 考前突击的底层逻辑先搞明白这门课到底考什么很多人一上来就抱着教材从第一章啃结果第一章的数学预备知识就劝退了。突击的第一原则是别按教材顺序复习按考试分值分布复习。把有限的十几个小时砸在分值最高、最容易拿分的模块上才叫突击。1.1 从题型分布倒推复习优先级算法设计与分析这门课的期末卷子绝大多数学校的结构都很稳定基本逃不出下面这几类题。我把它们按提分效率排了个序也就是单位复习时间能换回多少分。题型大致分值占比复习性价比说明复杂度计算与递推式求解15%~25%极高公式固定练几道就能上手算法过程手推填表类20%~30%高动态规划、矩阵连乘、最短路填表简答与概念辨析10%~15%中P/NP/NPC、贪心与DP区别算法设计与伪代码20%~30%中现场设计手写代码证明题10%~15%低正确性证明、归约证明临场难速成从这个表能看出来复杂度计算和过程手推两块加起来往往就占了一半分。这两块的特点是套路化、可训练、有标准答案。你花两个小时把主定理和常见递推式练熟可能比啃一晚上NP完全性拿的分还多。所以突击的路线很明确——先保复杂度计算再抠DP填表最后才碰证明题。有同学会问那编程题和设计题怎么办我的建议是把它们当成半背诵半理解来处理。考试里让你从零设计一个全新算法的概率其实不高更多是让你在经典算法上改一改比如在0-1背包基础上加一个约束。你把经典模板背熟改起来就有底气。1.2 突击和系统学习的区别在哪系统学习是从定义出发理解每个算法为什么被发明出来、解决了什么问题、正确性怎么证明。突击完全相反它是从考场上要写什么倒推回来。举个例子系统学习快速排序你要理解分治思想、划分策略、平均复杂度推导而突击只需要你知道划分函数怎么写、最好最坏平均复杂度分别是多少、什么情况下退化成O(n²)。这不是说突击可以不求甚解而是说突击要把理解压缩到够用的程度。我的经验是突击时对每个算法问自己三个问题就够了它解决什么问题、它的核心步骤是什么、它的复杂度是多少。这三个问题能答上来简答和计算题基本就稳了。真正需要深挖的只有一类——你算不准复杂度的算法那就必须把递推式老老实实推一遍。提示突击阶段千万不要试图把每个算法的正确性证明都看懂时间根本不够。证明题临场尽量写但别为它牺牲计算题的练习时间。2. 复杂度分析所有题目的地基必须先啃下来复杂度分析是这门课的地基也是突击阶段最值得先投入的地方。因为它几乎渗透在每一道题里——你写个伪代码老师要你标复杂度你做DP填表要分析时间复杂度你判断P和NP的关系也绕不开多项式时间。这块啃不下来后面全是空中楼阁。2.1 渐进符号和递推式求解渐进符号这一块考试基本就考三个O、Ω、Θ。定义要能说清楚但更重要的是会算。常见函数的增长速度排序必须烂熟于心考场上经常让你排序或者判断谁是谁的上界。记住这个顺序常数量级 对数 多项式 指数 阶乘具体展开就是 1 log n √n n n log n n² n³ 2ⁿ n!。递推式求解是重点中的重点。突击阶段你至少要熟练三种方法代入法、递归树法、主定理。代入法适合验证答案递归树法适合直观估算主定理适合快速出结果。我重点说主定理因为它是考场上最省时间的方法。主定理处理的是形如 T(n) aT(n/b) f(n) 的递推式其中 a≥1、b1。核心思路是比较 f(n) 和 n^(log_b a) 这两个量的大小关系第一种情况如果 n^(log_b a) 比 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) 更大且满足正则条件 a·f(n/b) ≤ c·f(n)那么 T(n) Θ(f(n))。光看定义容易晕我给个实战例子。归并排序的递推式是 T(n) 2T(n/2) Θ(n)。这里 a2b2n^(log_2 2) n而 f(n) Θ(n)两者同阶命中第二种情况所以 T(n) Θ(n log n)。再看二分查找 T(n) T(n/2) Θ(1)a1b2n^(log_2 1) n⁰ 1f(n) Θ(1)同阶命中第二种T(n) Θ(log n)。这两个是最经典的考法必须做到看题就能报答案。注意主定理不是万能的遇到 f(n) 落在三种情况缝隙里的递推式比如 T(n) 2T(n/2) n log n主定理失效这时候只能老老实实用递归树或代入法。考试里这种故意不让你用主定理的题偶尔出现看到 a 和 b 配出来的结果和 f(n) 差一个 log 因子就要警觉。2.2 递归树法的手推技巧递归树法是突击阶段必须掌握的第二把武器因为它既能算复杂度又能直观解释复杂度是怎么来的简答题里写出来很加分。以 T(n) 2T(n/2) n 为例画递归树的过程是这样的第一层代价是 n第二层分成两个子问题、每个代价 n/2加起来还是 n第三层四个子问题、每个代价 n/4加起来仍然是 n。每一层的代价都是 n一共分了 log₂n 层最后一层叶子代价是 Θ(n) 个常数于是总代价是 n·log n n Θ(n log n)。这个每层都是 n、一共 log n 层的直觉一定要建立起来考试时如果时间紧直接画两层说明每层代价相等、层数是对数级就能拿大部分过程分。递归树的另一个好处是能处理主定理覆盖不到的情况。比如 T(n) T(n/3) T(2n/3) n这不是标准的主定理形式但画树会发现每一层代价都是 n而最短路径是沿着 n/3 走到 1深度是 log₃n最长路径沿着 2n/3 走深度是 log_{3/2}n两边只差常数倍所以总复杂度还是 Θ(n log n)。3. 六大算法范式抓住每个范式的命门教材里通常会把算法分成若干设计范式分治、动态规划、贪心、回溯、分支限界再加上图算法里那些专门的算法。突击时不要平均用力每个范式只需要抓住它最典型的例题和最容易混的点。3.1 分治法与动态规划的区别和联系这两个是考试里最爱考、也最容易混的一对。核心区别在于子问题是否重叠。分治法的子问题是相互独立的各管各的解完再合并动态规划的子问题有重叠同一个子问题会被反复用到所以要用表格把中间结果存下来避免重复计算。我常用的一个类比是分治法像一个大项目拆成几个互不相干的小组各组独立干活最后项目经理把成果拼起来动态规划像一道数学题里有很多小台阶你踩过一次的台阶要记下来不然每次都重新算就慢死了。分治法的高频例题就那几个归并排序、快速排序、二分查找、最大子数组、最近点对、大整数乘法。突击时每个都要能默写出伪代码。动态规划的高频例题更集中矩阵连乘、最长公共子序列LCS、0-1背包、最长递增子序列、编辑距离、最优二叉搜索树。这几道题在期末卷里出现的频率高得惊人几乎是必考。3.2 动态规划填表的手推流程动态规划的手推过程是期末卷的送分题也是丢分题因为步骤多、容易算错。我用矩阵连乘和0-1背包这两道最典型的题把流程拆开讲。矩阵连乘的核心是填写二维表 m[i][j]表示从第 i 个矩阵乘到第 j 个矩阵所需的最少乘法次数。递推式是m[i][j] min{ m[i][k] m[k1][j] p_{i-1}·p_k·p_j }其中 k 从 i 取到 j-1。手推时的正确顺序是按链长从小到大填先填长度为2的对角线再填长度3一直填到长度 n。为什么必须按链长填因为长链依赖短链的结果短链没算出来长链的 min 就无从谈起。这个按子问题规模从小到大填表的思想是所有DP手推题的通用逻辑。0-1背包的核心表是 v[i][j]表示前 i 个物品、容量为 j 时的最大价值。递推式是如果第 i 个物品的重量 w_i j那么 v[i][j] v[i-1][j]否则 v[i][j] max(v[i-1][j], v[i-1][j-w_i] v_i)。手推时要注意容量维度通常从0填到背包总容量物品维度从上往下填每个格子取值只看它上方和左上方对应位置的结果。我踩过的一个坑是很多同学把 v[i-1][j-w_i] 记成 v[i][j-w_i]结果算出来的答案偏大因为前者保证了物品不重复放后者则允许重复放就变成了完全背包。这个细节一定要在考场上盯住。3.3 贪心、回溯、分支限界各自守哪块阵地贪心的命门是局部最优能不能推出全局最优也就是贪心选择性质和最优子结构。考场上判断一个贪心策略对不对最有效的办法是举反例。经典的贪心例题有活动安排、哈夫曼编码、最小生成树Prim 和 Kruskal、单源最短路Dijkstra、部分背包。要注意的是0-1背包不能用贪心因为按单位价值排序后装不满时的取舍会导致整体次优解这个反例一定要会举。回溯法本质上是有剪枝的深度优先搜索核心考点是解空间树的画法、剪枝条件的判断以及N皇后、子集和、图着色、旅行商这些经典题。考试让你画解空间树时务必标清楚哪些节点被剪掉了以及为什么这些剪枝理由往往就是得分点。分支限界和回溯的区别在于搜索策略回溯是深度优先分支限界通常用广度优先或优先队列并维护一个限界函数来控制搜索范围。突击阶段掌握0-1背包的分支限界和旅行商的分支限界就够了重点是理解限界函数怎么算比如用贪心解作为上界来剪枝。4. 图算法与NP理论概念辨析别丢分图算法和NP理论这两块计算题和概念题混杂突击时要分清哪些是需要手推的、哪些是纯背的。4.1 最短路与最小生成树的模板对比这块最容易混的是哪些算法处理带负权边、哪些用邻接矩阵、哪些用优先队列。我给一个速查表考场上直接对号入座。算法解决问题数据结构能否负权复杂度Dijkstra单源最短路优先队列否O((VE)log V)Bellman-Ford单源最短路边集能O(VE)Floyd多源最短路邻接矩阵能O(V³)Prim最小生成树优先队列无向图O(E log V)Kruskal最小生成树并查集无向图O(E log E)Dijkstra 为什么不能处理负权边因为它基于贪心一旦一个顶点被标记为已确定最短路径就不再更新而负权边的存在可能导致后面出现更短的路径破坏了这个前提。这个原因经常出现在简答题里。Floyd 的三重循环顺序也是考点k 那一层必须放最外层因为它代表允许经过的中间顶点集合如果放错层结果就错了。4.2 NP完全性背熟定义和经典归约NP理论这块突击就别想着深入理解了把定义和几个经典结论背熟最划算。必背的核心概念有P类问题能在多项式时间内解决的问题。NP类问题能在多项式时间内验证一个解是否正确的问题。NP完全问题NPC既是NP问题又是NP难问题。只要任何一个NPC问题能在多项式时间内解决那么所有NP问题都能。NP难问题NP-hard至少和NPC问题一样难但不一定属于NP。经典的NPC问题必须能报出来几个SAT布尔可满足性、3-SAT、团问题、顶点覆盖、哈密顿回路、旅行商问题、子集和问题。归约这块考试大概率只考从哪个问题归约到哪个问题你记住几条经典归约链就够了比如3-SAT归约到团问题、团问题归约到顶点覆盖、3-SAT归约到子集和。归约的方向千万别搞反是把已知的NPC问题归约到待证明的问题上才能证明待证明的问题也是NPC。5. 编程题突击手写代码的临场生存法则算法设计与分析的编程题通常是手写伪代码或C/C代码考察的是你能不能把脑子里的思路准确地落在纸上。这块的突击重点是模板化把高频算法写成自己顺手的固定格式考场上直接套。5.1 高频手写代码清单突击阶段最值得默写的几个代码模板按考频排归并排序和快速排序的分治框架包括 partition 函数。二分查找的两种写法闭区间和左闭右开。0-1背包的一维滚动数组优化写法。LCS 的二维DP填表。Dijkstra 的优先队列版。KMP 的 next 数组构造。二叉树的前中后序非递归遍历。我建议把每个模板手抄三遍抄的时候不要看答案抄完对照检查。抄写比看更有效因为手写代码这件事本身就是肌肉记忆考场上你的手比脑子更快。一维滚动数组的0-1背包尤其值得练因为它的内层循环必须逆序这个细节特别容易在紧张时写反for (int i 0; i n; i) for (int j W; j w[i]; j--) // 逆序保证物品只用一次 dp[j] max(dp[j], dp[j - w[i]] v[i]);如果这里写成正序就变成完全背包了这也是老师爱设的陷阱。5.2 手写代码的排版与验证技巧考场上写代码卷面质量和逻辑正确同样重要。我的经验是三点第一先写函数签名和参数说明让老师一眼看出你理解题意第二代码里关键步骤写注释尤其是循环变量的含义和边界含义老师看注释就知道你懂不懂第三写完自己用一个小例子走一遍我最常用的是 n3 或者数组长度等于3的小例子几步就能验证边界。实操心得手推小例子时专门检查三种边界——空输入、单元素、恰好等于某个临界值的输入。很多同学代码逻辑没错就是边界处理写错比如循环写成 i n-1 导致最后一个元素没处理白丢分。6. 考场应急与常见翻车现场突击的最后一步是把考场上最容易犯的错提前排掉。我把平时和考后复盘时发现的高频问题整理成一张速查表。翻车现场典型表现应急处理复杂度算错递推式套错主定理情况用 n8 代进去数一数操作次数DP填表方向错长链先填、依赖短链按子问题规模从小到大重填贪心策略错用了不满足贪心选择性质的策略快速举一个反例自检归约方向反把待证问题归约到已知问题记住已知→待证才有效代码边界错循环少跑一次或多跑一次用长度3的小例子手动跑关于复杂度算错我再补一个自查方法如果你算出来是 O(n log n)就代 n8log 层数是3每层大概是8次操作总数约24次量级对得上如果你算出来是 O(n)但代进去发现层数明显是 log 级那肯定错了。这种代数字验证数量级的习惯能救回不少计算题。时间不够时的取舍也是学问。我的策略是先扫一遍全卷把会做的题标记出来优先做计算题和填表题这两类分多且稳证明题和设计题放在最后能写多少写多少公式和思路写上去通常都有过程分千万别空着。有一次我留了一道证明题没写考后对答案发现论证的关键一步其实我会白白丢了六分从那以后我宁可写半页废话也不留空白——当然这里的废话指的是相关的公式和思路不是瞎写。很多同学问这门课到底能不能两天突击过。我的回答是及格线附近完全可以想拿高分就得靠平时。但如果你只是想过那上面这套重计算、轻证明、模板化编程的打法配合真题练习两天时间足够把及格线摸到。真正决定成败的其实不是聪明程度而是你有没有在最后48小时里把有限的注意力精准地砸在分值最高的模块上。