期末复习算法设计与分析很多人第一反应就是“背”。但背完复杂度公式、背完伪代码上了考场看到变式题照样懵。这门课真正的难点不在于“记住”而在于“看出这道题在考哪个算法模型然后熟练地把模板套上去”。我当年复习的时候也吃过亏啃了半个月教材结果考场上栽在一道动态规划的状态定义上。后来我把整门课的知识点、常见题型和答题套路重新整理了一遍用“考点例题模板”的方式过三轮效果立竿见影。这篇复习资料就是把那套东西完整复现出来覆盖分治、动态规划、贪心、回溯分支限界、复杂度分析这些核心板块每块都配了典型题和易错点适合期末冲刺也适合平时对照着查漏补缺。这篇内容面向的是正在准备算法设计与分析期末考试的计算机相关专业学生。如果你能把文中每一道例题都独立做出来再把每个模板的适用条件讲清楚那这门课的复习基本就到位了。要是你是考研党或者准备面试刷题这篇文章也能帮你把算法基础模型完整过一遍性价比极高。1. 先把复习框架搭起来考点分布与题型结构算法设计与分析这门课不同学校的教材版本可能不一样但核心考点高度趋同。我把近几年的期末真题和主流教材机械工业出版社的《算法设计与分析》、电子工业出版社的《计算机算法设计与分析》等对照过考试的重心非常集中就五大块复杂度分析、分治、动态规划、贪心、回溯与分支限界。图论算法Prim、Kruskal、Dijkstra、Floyd经常和贪心、动态规划混在一起考字符串匹配里的KMP也是高频考点这些都需要额外留意。1.1 高频考点权重分析先给一张我自己整理的考点权重表按照历年出现频率和分值占比排的你们复习的时候按这个优先级来分配时间考点模块常见题型分值占比约优先级渐进复杂度分析大O、大Ω、大Θ选择题、填空题、简答题10%-15%必拿分治策略二分、归并、快排、最近点对算法设计题、递归方程求解15%-20%必拿动态规划背包、LCS、矩阵连乘、编辑距离填表题、状态转移方程推导、算法设计20%-25%核心贪心策略活动安排、Huffman、最小生成树证明题、算法设计题、判断题15%-20%核心回溯与分支限界n皇后、图着色、旅行商搜索树画图、剪枝条件分析10%-15%重点KMP、堆排序等专项算法手动模拟题、计算题5%-10%挑战从这张表能看出来动态规划和贪心加起来能占到将近一半的分值是绝对的复习核心。这两个模块本身也是算法设计里最考验“建模能力”的部分后面我会重点展开。1.2 复习节奏怎么安排我建议的复习节奏是三轮法亲测有效第一轮约3天过基础概念和复杂度分析把渐进记号的定义、主定理、常见递推方程的解法彻底搞懂。这一轮的目标是能一眼看出算法的时间复杂度不需要纠结具体的证明细节。第二轮约4天主攻分治、动态规划、贪心三大算法设计策略。每天一个大模块把经典例题全部手推一遍。注意是手推不是看懂了就行。动态规划一定要自己完整地填一遍表贪心证明一定要自己写一遍这个过程决定了你考场上能不能把题做出来。第三轮约2天过回溯、分支限界、KMP这些相对零散但必考的点再加上前两轮的错题回顾。这个阶段重点记忆典型题目的答题模板和格式保证考场上写出来的过程是规范的。2. 复杂度分析别在送分题上丢分复杂度分析是这门课的基石也是考试最容易拿分也最容易失分的地方。说它容易拿分是因为题型固定、套路清晰说它容易失分是因为大家对渐进记号的理解往往停留在“知道定义”一到具体判断就模棱两可。2.1 渐进记号的核心区别大O记号表示上界可以用来描述算法时间复杂度的最坏情况大Ω记号表示下界描述最好情况大Θ记号则是上下界都成立表示算法的渐进紧确界。这三个定义考试必考选择题和填空题经常混在一起出解题的关键是看清题目问的是“最坏情况”还是“最好情况”再决定用哪个记号。举个例子快速排序的时间复杂度最坏情况是O(n²)最好情况是Ω(n log n)但平均情况和最好情况都可以用Θ(n log n)来描述。如果题目问“快排的时间复杂度是多少”最稳妥的答法是“平均情况Θ(n log n)最坏情况O(n²)”千万别只写一个“O(n log n)”那样是不严谨的。2.2 递推方程求解主定理是万能钥匙分治算法的时间复杂度分析必然落到递推方程的求解上这是简答题的常客。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) O(n)。这里a2b2f(n)O(n)n^(log_2 2) nf(n)和n^(log_b a)同阶所以答案是Θ(n log n)。注意主定理用不了的时候比如a不是常数、f(n)不满足多项式关系就用递归树法或者代换法。考试如果出这类题通常不会太难代换法加上数学归纳法基本能解决。2.3 常考复杂度速查表这份表我备考时贴在桌上天天看考前一天再默写一遍保证选择题秒杀算法时间复杂度空间复杂度二分查找O(log n)O(1)归并排序O(n log n)O(n)快速排序平均O(n log n)最坏O(n²)O(log n)递归栈堆排序O(n log n)O(1)0-1背包动态规划O(nW)O(nW)矩阵连乘O(n³)O(n²)Dijkstra朴素O(V²)O(V)KMPO(nm)O(m)3. 分治策略递归三部曲与经典题型分治的核心理念就十二个字分解、解决、合并。但实际做题时难点往往不在“怎么分”而在“怎么合并”。期末考试里分治算法的题目设计题和复杂度分析题都常考重点集中在二分查找、归并排序、快速排序、最近点对这几个经典算法上。3.1 分治算法的设计套路分治算法的代码我习惯用三部曲来写这个模板在考场上特别好用def divide_and_conquer(problem): # 第一步递归出口问题足够小时直接解决 if problem is None or len(problem) 1: return solve_trivially(problem) # 第二步分解问题为若干子问题 left divide(problem[:mid]) right divide(problem[mid:]) # 第三步合并子问题的结果 return merge(left, right)考场上写伪代码的关键是“结构清晰三步走”阅卷老师按点给分你把递归出口、分解、合并三个步骤写得明明白白就算细节有点小瑕疵也能拿大部分分。3.2 归并排序与逆序对老题新考归并排序本身不难但它的一个经典变式——求逆序对——是期末和考研都喜欢出的题目。题目描述一般是“给定一个数组求其中逆序对的数量”这里的逆序对就是满足ij且a[i]a[j]的数对。思路是在归并排序合并的时候顺带计数。当右半部分的元素要放到前面时说明左半部分剩下的所有元素都比它大这些元素跟它都构成逆序对一次就能统计完。核心代码长这样def merge_sort_count(arr, left, right): if left right: return 0 mid (left right) // 2 count merge_sort_count(arr, left, mid) merge_sort_count(arr, mid1, right) # 合并两个有序子序列同时统计逆序对 temp [] i, j left, mid 1 while i mid and j right: if arr[i] arr[j]: temp.append(arr[i]) i 1 else: # 左边剩下的都大于arr[j]都构成逆序对 count mid - i 1 temp.append(arr[j]) j 1 while i mid: temp.append(arr[i]) i 1 while j right: temp.append(arr[j]) j 1 arr[left:right1] temp return count这个变式题的关键在于理解“为什么当a[i] a[j]时a[i..mid]全部都与a[j]构成逆序对”——因为左右两部分都是有序的如果a[i]已经大于a[j]那a[i]后面的所有元素也都大于a[j]。理解了这一点代码写起来就很自然了。3.3 最近点对问题分治合并步骤的经典最近点对问题在期末考试中偶尔会出简答题或者中等难度的设计题给定平面上n个点找出欧几里得距离最近的两个点。暴力法是O(n²)分治法能做到O(n log n)。分治的思路是按x坐标排序把点集分成两半递归求左右两半的最小距离d1和d2取d min(d1, d2)合并步骤是重点只需要检查跨过分界线的那些点。具体做法是取出所有与分界线x坐标距离小于d的点按y坐标排序然后对每个点只检查它后面的最多7个点这是个几何结论需要记住合并这一步为什么只需要检查常数个点因为左右两半内部已经满足距离至少为d所以在宽度为2d的带状区域内任意一个点附近能落下的点数量是有限的。这个结论考试可能会让你解释要记清楚。3.4 分治算法的易错点我觉得分治这部分最容易被扣分的点有两个。第一个是递归出口条件写错比如二分查找里left right还是left right搞错了就会死循环或者漏解。第二个是合并步骤考虑不周尤其是最近点对这类“难点在合并”的问题很多人递归部分写对了合并部分漏东漏西白白丢分。4. 动态规划从填表到状态定义核心考点全覆盖动态规划是算法设计与分析期末考试的重头戏也是大家普遍觉得最难的部分。说它难是因为动态规划题目没有固定的模板每道题的状态定义和状态转移方程都不一样。但反过来说期末考试中动态规划考察的题型其实是高度固定的就那么几类经典问题。把这些问题的“状态定义-转移方程-初始化-遍历顺序”四件套吃透拿分就不难了。4.1 动态规划的解题四步法我在做动态规划题目时永远按照四个步骤来思考群里的学弟学妹用了也说好第一步定义状态。明确dp[i]或dp[i][j]表示什么含义。状态定义是动态规划的魂定义好了后面都顺定义不好就卡死。比如0-1背包dp[i][j]表示前i件物品放入容量为j的背包能获得的最大价值。第二步写状态转移方程。这是核心也是考试给分最多的地方。0-1背包的转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])其中w[i]是重量v[i]是价值。第三步确定初始化条件。比如dp[0][j] 0没有物品可选时价值为0dp[i][0] 0背包容量为0时价值为0。第四步确定遍历顺序。0-1背包的遍历顺序是外层先遍历物品、内层遍历背包容量内层的容量要倒序遍历一维滚动数组的情况下。4.2 高频考点10-1背包问题0-1背包是动态规划里最经典的题目没有之一。很多学校的期末考试大题直接就是“给定物品重量和价值求背包能装下的最大价值”或者变形成“分割等和子集”、“目标和”这类问题。用二维数组实现0-1背包是考试写代码的最稳妥选择def knapsack(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, capacity 1): if j weights[i-1]: dp[i][j] dp[i-1][j] else: dp[i][j] max(dp[i-1][j], dp[i-1][j - weights[i-1]] values[i-1]) return dp[n][capacity]如果题目要求额外输出选择了哪些物品就再维护一个choices数组当dp[i][j]取的是“选了第i件物品”那个值时就在choices[i][j]里记录1最后倒着回溯就能得出选择了哪些物品。注意期末考试问“为什么0-1背包不能用贪心算法”这是判断题/简答题的高频题。标准答法是0-1背包问题不具有贪心选择性质按单位重量价值贪心不能保证全局最优举一个反例即可比如容量50有物品A重30价值60物品B重20价值100物品C重50价值110的情况。4.3 高频考点2最长公共子序列LCSLCS是另一个各校钟爱的考点。这类题通常要求画出dp表格然后根据表反推最长公共子序列的内容。状态定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。转移方程分两种情况if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])一种帮助理解的想法是text1的当前位置和text2的当前位置相同那就一定可以把这个字符加入到公共子序列中不同的时候就分别试试“去掉text1当前字符”和“去掉text2当前字符”哪个的结果更长。考试时如果让画表格一定要注意填表的方向是从左上到右下逐行填充每一格只依赖左、上、左上三个方向的值这个特点在反推子序列的时候会用到。4.4 高频考点3矩阵连乘与区间DP矩阵连乘问题矩阵链乘法是区间动态规划的入门题也是期末考试常客。特点是dp状态不再是一维而是定义在区间上的二维状态。题目描述是给定n个矩阵的维度序列求完全括号化方案使得乘法次数最少。状态定义dp[i][j]表示从第i个矩阵到第j个矩阵的最小乘法次数。转移方程dp[i][j] min(dp[i][k] dp[k1][j] p[i-1] * p[k] * p[j])其中k从i到j-1遍历。这个方程的含义就是把区间[i,j]分成[i,k]和[k1,j]两部分先分别算出两部分的最小乘法次数再加上这两部分相乘的代价。区间DP的遍历顺序比较特殊不是普通的从小到大而是先遍历区间长度再遍历起点。因为计算长区间的值需要用到短区间的结果所以要保证短区间先算完。4.5 高频考点4编辑距离编辑距离Levenshtein距离在期末考试中的出现频率逐年上升因为这道题把动态规划三要素——状态、转移、初始化——都考全了。状态定义dp[i][j]表示word1的前i个字符转换成word2的前j个字符所需的最少操作数。操作有三种插入、删除、替换。转移方程if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1三种操作和三个子问题的对应关系是dp[i-1][j] 1是删除操作word1的前i-1个字符已经是word2的前j个字符删掉第i个即可dp[i][j-1] 1是插入操作word1的前i个字符已经是word2的前j-1个字符再插入一个字符即可dp[i-1][j-1] 1是替换操作把word1第i个字符替换成word2第j个字符。初始化时dp[i][0] i全部删除dp[0][j] j全部插入。这里的初始化恰恰对应了一个字符串为空时的情况理解了这个初始化就不会错。4.6 动态规划做题的常见卡壳点动态规划这部分常见的卡壳点有两个。第一个是状态定义太模糊比如一上来就定义dp[i]是“前i个元素的最优值”但没想清楚第i个元素到底取不取。映射到具体题目上就是最长上升子序列LIS和最大子数组和的dp定义方式不同一个是dp[i]表示以i结尾的LIS长度一个是dp[i]表示以i结尾的最大子数组和。你要是把两者的定义搞混了整个转移方程就全盘皆输。第二个卡壳点是空间优化的方向搞反了。0-1背包用一维数组时容量要倒序遍历完全背包却要正序遍历这个区别的本质是物品能被使用一次还是无限次理解了这一点就不容易弄反。5. 贪心策略证明比算法更重要贪心这一章期末考试题目的风格和动态规划完全不同。动态规划重在建表和代码贪心则更看重证明能力。很多同学学贪心容易产生一个错觉——“贪心就是每步取最优嘛代码很短很简单”。但考试可不是让你写代码那么简单而是让你证明“为什么贪心选择能导向全局最优解”。这部分需要引起重视。5.1 贪心算法的两个核心性质贪心算法能成立的核心性质有两个考试简答题必考贪心选择性质通过一系列局部最优选择能产生全局最优解。证明方法通常是假设有一个全局最优解证明可以通过替换其中的某一步把它变成一个贪心选择加上剩余子问题的最优解。最优子结构性质一个问题的最优解包含其子问题的最优解。这个性质动态规划也有但贪心需要更强的条件即“贪心选择之后剩余子问题和原问题同构且可以继续用贪心”。考场上遇到“证明贪心算法正确性”的题标准三步是第一步证明贪心选择存在最优解第二步证明贪心选择后剩余子问题的最优解与贪心选择的组合能构成原问题的最优解第三步用数学归纳法收尾。5.2 活动安排问题贪心入门必考活动安排问题是贪心算法最经典的入门例题也是期末考试选择题和简答题的最爱。问题描述是给定一系列活动的开始时间和结束时间求最多能安排多少个互不冲突的活动。贪心策略是每次选择结束时间最早且与已选活动不冲突的活动。为什么按结束时间最早而不是按开始时间最早或者持续时间最短因为结束时间越早给后面的活动留出的时间越多这是直观理解。严格证明需要用到交换论证法。这个贪心算法的时间复杂度是O(n log n)瓶颈是排序。5.3 Prim算法和Kruskal算法最小生成树的贪心美最小生成树MST问题在期末考里几乎每年都出现两种解法Prim和Kruskal都基于贪心思想但贪心的角度不同。热搜词里有“prim算法”看来确实是大家的重点关注对象。Prim算法的贪心策略是从一个顶点出发每次选择连接“已经在树中的顶点”和“不在树中的顶点”的最短边加入。它每次找的都是“生长”出一条最短边让树逐步长大。时间复杂度是O(V²)朴素实现用二叉堆优化后是O(E log V)。Kruskal算法的贪心策略是把所有边按权值从小到大排序每次取最小权值的边如果加入后不会形成环就保留。判断是否会形成环用的是并查集。时间复杂度O(E log E)瓶颈在排序。考试如果问“为什么Kruskal算法需要并查集”答案是需要快速判断一条边的两个端点是否已经在同一个连通分量中如果不判断就会成环。这两种算法的对比表算法贪心策略数据结构时间复杂度适用场景Prim从已选顶点集合出发找最短连接边优先队列/数组O(V²)或O(E log V)稠密图Kruskal全局边排序后从小到大尝试并查集O(E log E)稀疏图5.4 Dijkstra算法贪心策略的限定条件Dijkstra算法是最短路径问题中的贪心算法也是期末考试的重点。它的贪心策略是每次从未确定最短路径的顶点中选取距离源点最近的那个加入已确定集合。但Dijkstra算法有一个重要的使用前提图中不能有负权边。为什么因为一旦有负权边贪心选择的“当前最近”可能不是全局最近——绕一条负权边再走一段可能比当前的直接路径更短。这一点是判断题和概念题的高频考点。考试时如果遇到“Dijkstra算法为什么不能处理负权边”标准答法就是举一个带负权边的简单图反例然后用“每次贪心选出最近顶点能成立依赖边权非负”来解释。Dijkstra朴素实现的时间复杂度是O(V²)用优先队列优化后是O((VE) log V)。考试问复杂度时要注意说清楚是哪种实现。5.5 贪心与动态规划的分界线在哪考试特别喜欢出一道区分题给你一个问题问应该用贪心还是动态规划。比如0-1背包动态规划和分数背包贪心按单位重量价值排序取。分数背包为什么能用贪心而0-1背包不能用区别在“可分割性”。分数背包的物品可以切分所以局部最优选择单位价值最高的物品一定能进入全局最优解而0-1背包的物品是不可分割的选了单位价值最高的可能占用大量空间反而导致整体价值降低。这类题的回答套路是先说明问题的约束条件可分割/不可分割再说明贪心选择性质是否成立最后给出结论。不要只背结论要把理由说清楚阅卷是按点给分的。6. 回溯与分支限界搜索树的构造与剪枝回溯和分支限界是算法设计策略中相对独立的一块期末考试题型主要是两种一是给一个具体问题如n皇后让你画出搜索树/解空间树标注剪枝条件二是给一段回溯伪代码让你分析时间复杂度或者找出某个节点的解。6.1 回溯算法的通用模板回溯算法的核心是深度优先搜索加剪枝代码模板可以背下来def backtrack(path, choices, result): if is_goal(path): result.append(path[:]) return for choice in choices: if is_valid(choice, path): # 剪枝条件 make_choice(path, choice) backtrack(path, choices, result) undo_choice(path, choice) # 撤销选择这个模板适用于全排列、子集、组合、n皇后、数独等所有回溯问题。考试写伪代码时把“判断是否到达目标”、“遍历可选列表”、“合法性检查”、“做选择”、“递归”、“撤销选择”这六步写清楚就行。6.2 n皇后问题最经典的回溯考题n皇后问题是回溯算法的经典代表。题目描述是在n×n的棋盘上放置n个皇后使得任意两个皇后不能互相攻击即不在同一行、同一列、同一对角线上。回溯策略是逐行放置皇后每行尝试所有列如果当前位置合法就继续下一行不合法就回溯。关键点在于合法性检查比较容易漏掉的条件是两条对角线的判断。判断位置(row, col)是否与前面放置的皇后冲突需要满足三个条件任意两个皇后不能在同一列不能在同一主对角线行号-列号相同不能在同一副对角线行号列号相同。def solve_n_queens(n): result [] col_used [False] * n diag1 [False] * (2 * n - 1) # r c diag2 [False] * (2 * n - 1) # r - c n - 1 def backtrack(row, path): if row n: result.append(path[:]) return for col in range(n): if col_used[col] or diag1[row col] or diag2[row - col n - 1]: continue col_used[col] diag1[row col] diag2[row - col n - 1] True path.append(col) backtrack(row 1, path) path.pop() col_used[col] diag1[row col] diag2[row - col n - 1] False backtrack(0, []) return result画搜索树的时候注意树的第i层对应第i行每个节点的分支对应该行尝试的列号。n皇后回溯的时间复杂度是O(n!)因为第一行有n个选择第二行最多n-1个以此类推。分支限界和回溯的区别在于分支限界常用于求解最优化问题且会用限界函数下界/上界来剪枝而不只是合法性检查。6.3 0-1背包问题在回溯法中的表现0-1背包既能用动态规划解也能用回溯法解。期末考偶尔会出一道“用回溯法求解0-1背包并画出搜索树”的题目这时候要注意回溯法求解0-1背包解空间树是一棵子集树每个节点的分支表示“选或不选”当前物品。搜索时如果当前已装重量加上剩余物品中最轻的或者按上界函数估计的都达不到当前最优值就可以剪枝。最常用的剪枝是计算当前节点的“上界”如果上界小于当前已知最优值就剪掉。这种情况下分支限界法和回溯法的区别就很清晰了对比项回溯法分支限界法搜索方式深度优先广度优先/最佳优先剪枝依据约束条件目标函数界约束条件限界函数适用问题组合优化、可行解搜索最优化问题存储结构栈递归栈队列/优先队列6.4 剪枝函数的设计思路剪枝是回溯算法的灵魂考试简答题爱问你“该问题使用了哪个剪枝函数”。标准的剪枝函数就两类约束函数在扩展节点时剪去不满足约束的子树限界函数剪去得不到可行解或最优解的子树。比如图着色问题约束函数就是检查“当前顶点拟用的颜色和已经染色的相邻顶点颜色是否冲突”旅行商问题TSP的限界函数通常用“当前已走路程剩下未访问城市的最短路程下界”来剪枝。7. 高频专项算法KMP、堆排序与排序算法对比除了上面几大算法策略还有一些具体的算法在期末考试中会单独出题这些题目通常不需要你设计新算法而是考察你是否理解算法的工作过程和能手动模拟执行过程。这部分内容相对机械但也最容易拿满分属于“背下来就能得分”的类型。7.1 KMP算法的核心与next数组计算KMP算法的热搜度非常高原因是很多学校把它作为“字符串匹配”知识点的必考内容。期末考题一般分两问一是手动计算next数组二是用KMP算法模拟匹配过程。KMP的核心思想是当匹配失败时利用已经匹配的部分前缀信息让模式串向右滑动尽可能远的距离而不是像朴素匹配那样只移动一位。这个“已经匹配的部分前缀信息”就是next数组有些教材也用fail数组或部分匹配表PMT表示。next[i]的计算方法是对于模式串P[0..i]求最长的相同真前后缀的长度。手动计算建议用递推法从i1开始如果P[i] P[next[i-1]]则next[i] next[i-1] 1否则回退到next[next[i-1]]继续比较。以模式串ABABACA为例它的next数组计算如下位置i字符最长相同真前后缀next[i]0A无01AB无02ABAA13ABABAB24ABABAABA35ABABAC无06ABABACAA1考试时如果让模拟KMP全过程用next数组来更新模式串位置当主串位置i和模式串位置j失配时令j next[j - 1]然后继续比较如果j0则i。7.2 堆排序建堆、调整与排序全过程堆排序也是期末考试的高频题常以“给定数组用堆排序从小到大排序写出每一趟的结果”的形式出现。堆排序分两步建堆和堆调整。建堆有两种方式自底向上从最后一个非叶子节点开始从下往上做下沉调整时间复杂度O(n)。另一种是自顶向下逐个插入建堆时间复杂度O(n log n)。考试一般考第一种。然后重复n-1次把堆顶最大元素和堆尾交换把堆的大小减一然后对堆顶做下沉调整。每趟结束后数组末尾就多了一个已经排好序的元素。以数组[5, 3, 8, 4, 1, 9]为例构建大顶堆后堆顶是9第一趟交换9和1然后对前5个元素调整堆……考试要求写出每一趟的结果做题时要标明“已排好序的部分”和“剩余堆的部分”。7.3 排序算法大对比复杂度、稳定性、适用场景排序算法几乎是每所大学的必考点选择题和填空题都喜欢出对比题。我整理了一份对比表考前背一遍选择题基本不会失分排序算法平均时间最坏时间空间稳定性特点冒泡排序O(n²)O(n²)O(1)稳定代码简单适合n很小选择排序O(n²)O(n²)O(1)不稳定交换次数最少插入排序O(n²)O(n²)O(1)稳定基本有序时接近O(n)希尔排序O(n^1.3)O(n²)O(1)不稳定插入排序的改进归并排序O(n log n)O(n log n)O(n)稳定适合外部排序快速排序O(n log n)O(n²)O(log n)不稳定内部排序首选堆排序O(n log n)O(n log n)O(1)不稳定借助堆结构计数排序O(nk)O(nk)O(k)稳定数据范围小基数排序O(d(nr))O(d(nr))O(nr)稳定位数少“快排最坏情况什么时候出现”——当每次划分都极度不均衡时比如数组已经有序且每次选第一个元素作为基准时时间复杂度退化为O(n²)。这个问题的标准回答一定要写上“可以通过随机选择基准来避免”。8. 考场实战典型大题完整解答示范复习到最后最重要的一步是用标准答题格式来做几道完整的大题。我在这里给出一道典型的期末综合大题解答这道题融合了动态规划、贪心、回溯等多个知识点很有代表性。8.1 典型题10-1背包的三种解法对比题目有4个物品重量分别为2、3、4、5价值分别为3、4、5、6背包容量为8。求最大价值。解法一动态规划填表法按行填写dp表表格如下物品\容量0123456780件000000000第1件(w2,v3)003333333第2件(w3,v4)003447777第3件(w4,v5)003457899第4件(w5,v6)0034578910最大价值是10回溯可知选择的是第2件、第3件或者第1件、第3件、第4件也满足条件需要根据choices数组具体判断。解法二回溯法解空间树是一个子集树总共有2^416个叶子节点但通过重量约束和上界剪枝实际只需搜索一部分节点。解法三贪心法按单位重量价值排序后取物品得到的结论是选择物品1和物品2总重量5总价值7。可以看到贪心结果10不是最优解。这说明0-1背包不具有贪心选择性质。这道题如果作为大题出通常第一问让动态规划求解第二问让判断贪心是否正确并说明理由。8.2 典型题2活动安排问题的完整证明题目有5个活动开始时间和结束时间如下表求能安排的最多活动数。活动开始时间结束时间A14B35C06D57E89按照“结束时间最早”贪心策略排序后活动顺序为A1-4、B3-5、D5-7、C0-6、E8-9。依次选择先选A然后跳过B因为与A冲突选择D与A不冲突跳过C最后选择E与D不冲突。最优解是{A, D, E}共安排3个活动。解答这类题时千万不要只写“答案是3”要把选择过程每一步的决策依据都写出来阅卷老师按决策过程的正确性给分。9. 考前24小时最容易丢分的五个细节最后这部分写给临时抱佛脚的同学也写给所有想在考前几天再提提分的同学。根据我批改作业和考试的经验以下五个细节是大家最常踩的坑。第一复杂度分析不写单位。比如“快速排序时间复杂度是O(n log n)”只写对了答案的一半最好补上“平均情况下”同时指出“最坏情况是O(n²)”。很多同学的失分点就在“只说了平均情况没提最坏情况”。第二动态规划的边界条件初始化错误。特别是dp[0][j]、dp[i][0]这些边界值不仔细想就写0结果在某些题目中边界值应该是整数MIN或MAX。比如编辑距离的dp[0][j] j最长递增子序列的dp[i] 1每个元素自身长度为1。边界条件是给分的重点绝对不能丢。第三回溯算法的撤销步骤遗忘。考试写回溯代码时做了选择之后如果不写撤销代码整个搜索树就全乱了。我自己的习惯是“做选择”和“撤销选择”两行代码同时写完再往下看这样永远不会漏。第四KMP的next数组和失配时模式串的移动位置搞混。next[i]表示的是“当第i个字符失配时模式串应该回退到的位置”不是“已经匹配的字符个数”。这里的细微差别考试时很容易把j next[j-1]写成j next[j]。第五排序算法稳定性记忆混淆。有一个顺口溜可以参考冒泡、插入、归并、计数、基数稳定选择、希尔、快排、堆排不稳定。稳定的排序算法在“键值相同情况下能保持原始相对顺序”的场景中有独特价值比如多关键字排序。我个人在考前的习惯是不刷任何新题只看错题和自己的笔记。新题只会增加焦虑看错题能时刻提醒自己容易在哪个环节翻车。这一步看起来很简单但对考试成绩的提升是最直接的。另外一个小技巧是考试时先做计算量小的题比如复杂度分析、KMP模拟把稳拿的分先攥在手里再去做动态规划填表或者写大题。算法设计题一旦卡住容易心态爆炸先拿基础分能有效保证整场考试的节奏不出问题。算法的学习没有捷径但考试是有规律的。把每个经典模型的套路练熟把每个模板的适用边界搞清楚考场上面对变式题就不会慌。祝大家期末顺利都能拿到理想的成绩。