1. 课程核心内容与复习思路拆解1.1 西电这门课到底在考什么先说个扎心的事实大多数同学在算法设计与分析这门课上栽跟头不是题做得不够多而是没有搞清楚这门课和其他编程课的区别。西电这门课的重点从来不只是“写代码”而是用科学方法分析算法“为什么快”“为什么省”外加掌握几大类经典算法的设计范式。我当年复习时踩过一个大坑花了一堆时间刷LeetCode结果期末卷子上的题和算法竞赛完全不一个路数。西电期末的算法题更“规范”偏重经典场景比如矩阵连乘、0-1背包、活动安排、n皇后这类教材原题变体。你要做的是把这几个经典模型的推导过程彻底吃透而不是整天去刷偏题怪题。从考点权重来看一般会集中在如下几个模块复杂度分析大O记号、时间复杂度递推方程求解递归树、主定理分治法划分-解决-合并的套路典型代表归并排序、快速排序、最大子数组动态规划状态定义、转移方程、填表顺序典型代表矩阵连乘、LCS、0-1背包贪心算法贪心选择性质的证明思路典型代表活动选择、哈夫曼编码回溯与分支限界解空间树模型、剪枝条件典型代表n皇后、0-1背包图算法部分学期重点Dijkstra、Floyd、Prim、KruskalNP完全理论一般只考概念P类、NP类、NPC问题、规约思想复习时不要平均用力。我建议把动态规划和分治法作为头号重点其次是贪心和回溯。这两块能出的题型多、分值大而且跟期末编程题强相关。1.2 复习资料怎么用才高效西电的教材一般是用机械工业出版社的《算法设计与分析基础》或者本校老师自己的讲义配套PPT往往信息密度很低每页就几个概念。我的经验是PPT用于圈定考点范围真正的理解必须靠教科书加自己动笔推导。为了方便复习我整理了一个“三遍法”第一遍快速过PPT和教材目录把每个章节的经典算法和对应复杂度圈出来形成一张考点地图。第二遍对每个经典算法自己拿草稿纸推导一遍时间复杂度。比如归并排序的T(n)2T(n/2)O(n)必须做到不看书也能用递归树和主定理两种方法求解。第三遍动手写代码实现重点算法尤其是动态规划的填表过程然后用几个测试用例验证。如果时间紧张只能选一件事做那就做第三遍。因为期末编程题就是把这些经典算法现场写出来你只要能把矩阵连乘和LCS的代码默写出来基本就稳了。2. 复杂度分析一切算法的地基2.1 渐近记号怎么用才算真正掌握很多同学觉得复杂度分析很简单就是数循环层数。但实际上西电考试喜欢考递推方程求解或者给你一段代码让你算精确的比较次数。渐近记号里最容易混淆的是大O、大Ω、大Θ三个符号。我的记忆方法是大O是“不超过”大Ω是“不少于”大Θ是“恰好等于同一个量级”。做题时题目说“时间复杂度的上界”就用O说“至少需要多少操作”就用Ω说“渐进紧确界”就用Θ。还有一个高频考点是复杂度大小比较。常考的顺序是O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)。你得会用极限法比较比如n log n和n^(1.5)取对数后就能看出后者大。期末题里经常让你排列几个复杂度的大小这种送分题别丢。考场上经常出现的一个隐藏扣分点忽略系数和低阶项后还要注意循环变量的变化方式。像这种代码for (i 1; i n; i * 2) { for (j 0; j i; j) { // 常数操作 } }外层循环次数为log n内层总共执行约2n次所以总复杂度是O(n)不是O(n log n)。这种题就是专门坑“想当然”的选手。2.2 递推方程求解递归树与主定理实战递归方程求解是西电期末必考的题型通常出现在选择题或填空题里有时也会在算法设计题里要求你写出复杂度。递归树法的思路很直观把每次递归调用的代价画成一棵树每层代价求和最后加起来。以归并排序为例T(n)2T(n/2)O(n)第一层代价n第二层两个子问题各n/2总代价n第三层总代价还是n这棵树一共有log n层所以总代价O(n log n)。主定理Master Theorem更快捷但要注意适用条件。对于形如T(n)aT(n/b)f(n)的递推式比较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) Ω(n^(log_b a ε))且满足正则条件则T(n)Θ(f(n))我当年复习时自己整理了几个常考的递推式并记住结论递推式结果适用方法T(n)2T(n/2)nΘ(n log n)主定理/递归树T(n)T(n/2)1Θ(log n)主定理T(n)2T(n/2)1Θ(n)主定理T(n)T(n-1)nΘ(n²)累加法T(n)2T(n-1)1Θ(2ⁿ)累加法对于不满足主定理的形式比如T(n)T(n/2)T(n/4)n用递归树展开也能得到O(n)因为每层总代价按比例递减为一个几何级数。这类题很有区分度建议你考前专门练几个。3. 分治法经典模型必须烂熟于心3.1 分治思想的本质与答题套路分治法在期末卷子里一般会出现一道大题可能是让你描述算法思想也可能是让你分析复杂度还有可能直接出一个用分治解决的实例。分治的核心步骤只有三步分解、解决、合并。考场上答题时最稳妥的框架是明确将一个规模为n的问题分解成几个规模为多少的子问题递归地求解每个子问题并写出递归边界base case说明如何将子问题的解合并成原问题的解写出递推式并分析时间复杂度这个框架一定要刻在脑子里。我见过太多同学上来就写代码却忽略了“为什么复杂度是这个量级”的说明结果被扣掉好几分。最容易被忽略的细节是递归边界。比如归并排序当区间长度为1时就停止划分快速排序当lowhigh时返回。如果边界没写对整个递归就崩了。期末编程题判分时很看重边界条件的判断。3.2 最大子数组问题期末编程题的高频原型最大子数组问题是分治法的一个典型应用西电期末编程题曾经直接考过。题目背景是给定一个整数数组找一个连续子数组使其和最大。朴素解法是三重循环枚举左右端点累加复杂度O(n³)。优化的前缀和写法能到O(n²)但分治解法能到O(n log n)。分治的思路是把数组从中点分成左右两半最大子数组要么完全在左边要么完全在右边要么跨越中点。前两种情况递归求解第三种情况从中点向左右两边扩展找最大和。这里有个关键代码实现细节int crossSum(vectorint nums, int left, int mid, int right) { int leftSum INT_MIN, sum 0; for (int i mid; i left; i--) { sum nums[i]; leftSum max(leftSum, sum); } int rightSum INT_MIN; sum 0; for (int i mid 1; i right; i) { sum nums[i]; rightSum max(rightSum, sum); } return leftSum rightSum; }注意跨越中点的连续子数组必须包含nums[mid]和nums[mid1]所以两边扩展的范围是确定的。这个细节经常有人写错把两个独立的连续区间拼接起来而实际上它们必须经过中点。不过期末如果只要求实现最大子数组的最佳解法其实是Kadane算法O(n)扫一遍即可int maxSubArray(vectorint nums) { int dp nums[0], ans nums[0]; for (int i 1; i nums.size(); i) { dp max(nums[i], dp nums[i]); ans max(ans, dp); } return ans; }这就是动态规划的思想了说明同一个题目用不同算法范式都能做。复习时最好把每个经典问题能做的方法都梳理一遍因为西电老师很喜欢考“一题多解”。3.3 归并与快排必须能默写的两个排序算法归并排序和快速排序是分治法的两大门面同时也是面试笔试的高频题。西电期末要么直接让你写其中一个要么让你比较它们在各种情况下的复杂度。归并排序的代码必须做到“闭眼能写”void merge(vectorint a, int left, int mid, int right) { vectorint tmp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (int p 0; p k; p) a[left p] tmp[p]; } void mergeSort(vectorint a, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); }注意mid的计算用left(right-left)/2防止溢出。归并排序的稳定性取决于合并时左半部分优先的写法上述代码中a[i] a[j]能保持稳定。快速排序的期望复杂度O(n log n)但最坏O(n²)。期末可能会考如何避免最坏情况比如随机选择基准、三数取中。西电期末考试对快排的考察更偏向于“快速排序在什么情况下退化”以及“为什么平均复杂度是O(n log n)”。用递归树解释每次划分越均匀递归树越平衡总代价越低。每次划分都为偏向一边递归树退化成单分支链表。4. 动态规划期末复习的重中之重4.1 动态规划与分治的本质区别动态规划在西电算法课程里占的比重至少30%几乎每张期末卷都有两道以上大题。很多同学把动态规划和分治搞混其实关键区别在于子问题是否重叠。分治法的子问题相互独立比如归并排序左右两半的排序结果互不影响。动态规划的子问题重叠比如0-1背包在决定装不装第i个物品时会反复使用前i-1个物品的最优解。如果还用分治递归就会重复计算大量状态。判断一道题是否用动态规划抓住两个性质最优子结构问题的最优解包含子问题的最优解重叠子问题不同决策路径会访问同一个子问题凡是能用动态规划的问题都可以通过画状态转移表来理解。我复习时的习惯是每个经典DP题都手动画表格比如LCS的二维矩阵、背包的二维表画完自然就理解状态转移过程了。4.2 矩阵连乘动态规划填表题的模板矩阵连乘问题是西电期末的“常青树”因为它能把动态规划的所有要素都考到状态定义、转移方程、填表顺序、记录决策、输出最优解。问题描述给定n个矩阵的维度序列求完全括号化的最小标量乘法次数。状态定义dp[i][j]表示第i个矩阵连乘到第j个矩阵的最小代价。转移方程dp[i][j] min_{k从i到j-1} { dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j] }其中p数组是维度矩阵Ai的维度是p[i-1]×p[i]。这里最容易被坑的是填表顺序因为dp[i][j]依赖更短的区间dp[i][k]和dp[k1][j]所以必须按区间长度从小到大计算而不能按行从上到下直接填。标准代码模板void matrixChain(int p[], int n) { vectorvectorint dp(n, vectorint(n, 0)); vectorvectorint s(n, vectorint(n, 0)); // 记录分割点 for (int len 2; len n; len) { // 区间长度 for (int i 1; i n - len 1; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { int cost dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j]; if (cost dp[i][j]) { dp[i][j] cost; s[i][j] k; } } } } // 最后构造最优解可用递归输出括号 }期末常考的第一问是“填写dp表”第二问是“给出加括号方式”。考前把上面代码和表格流程走上两遍这题基本就是送分。4.3 最长公共子序列LCS与0-1背包代码模板LCS是期末编程题的最高频出题点因为它代码短、思路清晰还能考回溯构造结果。状态定义dp[i][j]表示字符串A前i个字符和B前j个字符的最长公共子序列长度。转移方程若A[i-1]B[j-1]则dp[i][j]dp[i-1][j-1]1否则dp[i][j]max(dp[i-1][j], dp[i][j-1])代码实现时要特别注意下标dp的维度是(m1)*(n1)字符串下标从0开始所以判断字符时要用A[i-1]和B[j-1]。vectorvectorint dp(m1, vectorint(n1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (A[i-1] B[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } }如果需要输出具体的子序列可以额外用一个vector记录每个dp值来自哪个方向然后回溯。期末如果考到要求输出子序列时别只写长度要记得补全回溯函数。0-1背包更是“国民级”算法题。状态定义dp[i][w]表示前i件物品在容量为w的背包中能获得的最大价值。转移方程dp[i][w] max(dp[i-1][w], dp[i-1][w-w[i]] v[i])前提是ww[i]。常见的空间优化版本用一维数组倒序遍历for (int i 0; i n; i) { for (int w capacity; w weight[i]; w--) { dp[w] max(dp[w], dp[w - weight[i]] value[i]); } }为什么必须倒序因为正序会让物品i被重复使用。这个点西电爱考填空题或者选择题让你解释为什么这里要倒序。4.4 动态规划的期末大题常见变体期末不会生硬地考“0-1背包”而是会套一个实际场景。比如硬币找零问题完全背包每种硬币无限使用求最少硬币数编辑距离将字符串A变换成B的最小操作次数最长递增子序列LISO(n²)的DP版本西电的老师也喜欢考“总结递推关系”的题。比如给出一个具体的dp数组让你写出状态转移方程。这要求你不仅会写代码还要会用数学语言描述。我建议复习时把每个经典DP题的转移方程用“文字符号”写出来读起来越简洁越好。平时训练时养成习惯在代码旁边配一个“状态定义”和“转移方程”的注释考场上就能快速反应。5. 贪心算法与回溯概念辨析与经典应用5.1 贪心算法除了会写还要会证明贪心算法的代码往往比动态规划简单但它的难点在于“为什么贪心策略是对的”。西电期末对贪心的考察通常包含两部分一是让你设计贪心算法求某个问题二是让你说明贪心选择性质的证明思路。活动选择问题是最常见的例子。按结束时间排序后依次选择就能获得最多数量的相容活动。证明思路一般是贪心选择性质如果存在一个最优解包含最早结束的活动那么将贪心选择替换进去不会变差。然后用归纳法一步一步替换。期末答题时一个套路化的表述是先说明贪心策略比如“每次选取结束最早的活动”证明存在一个最优解包含这个贪心选择用归纳法证明每一步贪心选择都能保留最优解结构哈夫曼编码也是高频考点特别是构造哈夫曼树的过程。考试时给你一组字符和频率让你画出哈夫曼树并写出每个字符的编码。做这种题要记住每次从集合中选两个频率最小的节点合并新节点的频率等于两节点频率之和。合并过程中如果两个节点的频率一样一般可以把先出现的放左边这个约定不同教材有差异但只要你合并过程正确编码长度一样就行。5.2 回溯法解空间树与剪枝思路回溯法在西电期末的考点非常固定n皇后、子集和、0-1背包、图着色等。它本质是深度优先遍历解空间树加上剪枝函数约束函数和限界函数来减少搜索量。以n皇后为例解空间是一棵n叉树。在第k层确定第k个皇后放在哪一列每放一个就判断是否与前面已放的皇后冲突。冲突条件包括同一列、同一条对角线行差等于列差绝对值。核心代码模板bool place(int k) { for (int i 0; i k; i) { if (col[k] col[i] || abs(col[k] - col[i]) abs(k - i)) { return false; } } return true; } void backtrack(int k) { if (k n) { count; return; } for (int i 0; i n; i) { col[k] i; if (place(k)) { backtrack(k 1); } } }这里的剪枝就是place(k)函数提前排除冲突位置避免继续向下搜索无效分支。回溯法期末编程题一般不会要求跑大数据量的n但会要求你把剪枝条件写对。0-1背包的回溯解法则是用解空间树的左子树表示“装入背包”右子树表示“不装入背包”。需要设计一个上界函数比如当前价值剩余物品最高单位价值×剩余容量来判断是否值得进入右子树。这一部分在本科期末里通常只考思路不会让你写完整代码。5.3 分支限界法与回溯法的对比分支限界法在期末卷子里占比不大但偶尔会在选择题或判断题里出现。核心区别是搜索方式和目标不同回溯法深度优先用于找出所有解或任一解分支限界法广度优先或使用优先队列用于求最优解分支限界的关键是设计限界函数bound用来估计当前分支的下界或上界如果某分支的界比当前已知最优解差就剪掉。典型应用是旅行商问题和0-1背包问题。期末如果要比较两者记住一句话回溯法是“能不碰就不碰”分支限界法是“把每个节点都扩展一下能砍的再砍”。做题时画出搜索树标出剪枝节点就能拿分。6. 图算法与NP理论查漏补缺的重点区域6.1 最短路径Dijkstra与Floyd的适用场景西电算法课的图算法部分虽然篇幅不多但经常在期末选择或填空里出现。需要掌握两类最短路径算法Dijkstra单源最短路径要求边权非负。核心思想是贪心每次从未确定最短路的顶点中选出dist最小的顶点u然后松弛u的所有邻接边。时间复杂度朴素实现O(V²)优先队列优化O(E log V)。Floyd多源最短路径动态规划思想。状态dp[i][j]表示从i到j经过若干中间点的最短距离三层循环枚举中间点k。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][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];需要注意的是循环顺序中间点k必须放在最外层。这个点是西电常考的判断改错题。最小生成树部分Prim和Kruskal二选一。Prim适合稠密图Kruskal适合稀疏图。如果期末考试让你写伪代码优先写Kruskal因为它的实现更直观把所有边按权值排序从小到大选边用并查集判断是否形成环。6.2 NP完全理论不写代码也要拿分NP理论虽然抽象但西电期末一般只考定义和简单判断属于性价比很高的得分点。你需要记住以下几个基本概念P类问题能在多项式时间内求解的判定问题NP类问题能在多项式时间内验证一个解是否正确的问题NP完全问题NPC既是NP问题又能多项式时间规约到任何NP问题判断一个选择题是否为NPC常考的例子包括哈密顿回路、旅行商问题判定版本、图着色判定问题、背包决策版本、顶点覆盖。期末还可能考“什么叫多项式规约”。只要记住如果问题A可以在多项式时间内转换为B的实例那么B能解则A也能解记为A≤pB。当B是NPC时如果A能多项式时间求解则所有NP问题都能多项式时间求解即PNP。这一点的逻辑关系要理清别把方向搞反。实际准备这部分时我的建议是把课本上的概念用自己的话复述一遍再做几道判断和选择不用花太多精力。除非老师明确说NP理论出大题否则不要为了这个模块放弃了DP和分治。7. 期末题型分析与编程题实战模板7.1 西电期末题型分布与命题规律根据我和其他同学的经验汇总西电算法设计与分析的期末卷子一般分为四个部分选择题/填空题约30分覆盖概念、复杂度计算、算法性质判断简答题约20分比如“写出分治法的基本思想”“动态规划的两个性质是什么”综合题手工推导约30分比如矩阵连乘填表、哈夫曼树构造、DP画表编程题约20分一般是一道动态规划题或分治题要求写出可运行的代码编程题通常不会特别长但要求思路清晰、代码规范。老师阅卷时会看重状态定义是否清楚、循环边界是否正确、是否考虑了空数组或长度为1的边界情况。我在这里整理一份“期末编程题必须能默写的代码清单”算法代码行数核心易错点归并排序~25行merge时临时数组的索引恢复快速排序~15行基准选择和递归边界最大子数组(Kadane)~8行dp初值和答案初值LCS~20行下标从1开始0-1背包(一维)~10行容量倒序遍历矩阵连乘~20行区间长度len的循环写法n皇后~20行冲突条件判断Dijkstra(朴素)~30行未访问节点的选择和松弛考前最好在IDE里把这几个算法手打三遍以上每次都能不报错通过再换下一个。7.2 期末编程题的“套路化”解题步骤编程题虽然千变万化但解题步骤是固定的。我总结了一个四步法适用于大部分DP类编程题定义状态明确dp[i][j]代表什么下标范围是什么。找出转移方程想清楚当前状态可以由哪些状态转移而来边界条件是什么。确定遍历顺序判断是顺序、倒序还是按区间长度递增。构造答案确认要求输出的是最值、是否可行还是具体方案。拿“最长回文子串长度”举例定义dp[i][j]表示子串s[i...j]是否为回文转移方程是dp[i][j](s[i]s[j] (j-i2 || dp[i1][j-1]))。遍历顺序必须从短子串到长子串因为dp[i1][j-1]是更短的子串。这就是典型的按区间长度递增的遍历方式。编程题里还有一个容易被忽视的点空间复杂度。如果题目只要求输出最大长度你写一个二维表没问题但如果n上百亿二维肯定不行这时就要想到滚动数组优化。虽然西电期末不会出特别大的数据范围但在卷面上写“可用滚动数组优化空间到O(n)”是个加分项说明你理解DP的精髓。7.3 简答题的答题话术与踩分点简答题是很多人的丢分重灾区因为明明知识点会但写不到点子上。西电的简答题一般按踩分点给分所以尽量分条作答。给你几个常见的简答题答题模板问分治法的基本步骤答“分解、解决、合并”然后分别用一行解释每步做什么再举一个算法例子如归并排序来说明。问动态规划的两个要素答“最优子结构”和“重叠子问题”并各用一句话解释最好配对一个实际例子。问贪心算法与动态规划的区别从“全局最优与局部最优”“子问题重叠性”“是否回溯”三个角度比较。贪心只考虑当前最优不回溯动态规划考虑所有子问题通过比较选择最优。问回溯法与分支限界的联系答“都在解空间树上搜索”“都用剪枝思想”区别是搜索方式和适用目标不同。答题时要像写代码一样“结构化”。每条尽量独立、信息完整不要大片文字堆在一起。阅卷老师在快速扫题时能一眼看见你写的1、2、3点踩分就到位了。8. 复习时间规划与避坑指南8.1 考前两周的冲刺计划表有些同学问我只剩两周怎么办我的建议是分三个时间段第1到3天地毯式过概念。把PPT和课本的课后题做一遍尤其关注选择题和填空题确保基础概念零失误。第4到10天攻克核心算法。分治、DP、贪心、回溯各花两天每类算法找3-5个经典题不仅要做还要推导复杂度。第11到14天真题模拟。找前几年的期末题或者老师给的样卷按考试时间模拟重点练手速和代码书写。期末编程题最后几天再默写一遍每天默写2-3个算法保持手感。到了考场上你会发现其实很多代码已经形成肌肉记忆了。8.2 高频失分点与应对策略我整理了很多同学考后复盘得出的高频失分点这些坑提前避开至少能多拿10分复杂度写错归并排序写O(n log n)没错但快速排序没写“平均”两个字就被扣分。答题时一定要写明是平均、最坏还是最好。DP下标错位LCS中判断字符时用A[i-1]而不是A[i]0-1背包中状态转移时容量w要大于等于weight[i]。这些细节看起来小但在机器阅卷中能一眼看出代码是否有运行逻辑。回溯的剪枝不完整n皇后只判断列冲突忘了对角线冲突0-1背包回溯不写bound函数。期末大题的剪枝是得分点别省略。手写代码不带分隔符手写代码时如果不按“变量定义、初始化、循环主体、返回值”分段阅卷人找不到重点。建议用“//”注释标出状态定义和转移方程。概念题只写半句比如问“什么是NP完全问题”只写“能在多项式时间内验证”没写“是NP问题中最难的一类”就会丢分。我最后的体会是这门课不像数学分析那样纯靠天赋也不像大学物理那样需要大量计算它更像是一套通用的思维体操。你在复习过程中建立的“抽象问题、设计策略、评估效率”的能力未来无论做工程还是搞科研都非常有用。哪怕期末成绩不理想只要把分治、DP、贪心这几个范式的思路真正想明白了以后看很多系统设计、数据处理问题都会有一种“哦原来是这个套路”的豁然开朗感。所以别对着教材死记硬背一定要亲手推、亲手画、亲手敲。每画完一张DP表每默写完一遍归并排序你对算法的理解就会扎实一分。考试只是短期目标把算法设计的思维留在脑子里才是这门课真正留给你的财富。