企业官网建设流程全解析

期末复习这门课，最折磨人的不是题难，是不知道哪些东西会考、哪些公式要背到什么熟练度。我当年复习《算法设计与分析》的时候，教材翻了两遍，一上考场还是栽在递推方程上——题目看着眼熟，手一算就错。后来辅导过几届学弟学妹，发现大家踩的坑几乎一模一样。这篇东西我就按期末试卷的实际出题逻辑，把最常考、最容易扣分的模块拆开讲，每个模块配例题和答题思路，争取让你合上课本就能上手写题。

这篇内容的适用对象很明确：正在准备《算法设计与分析》期末考试、需要短时间把知识点串成答题能力的同学。不同学校卷面结构略有差异，但核心模块跑不出复杂度分析、分治与动态规划、贪心、回溯与分支限界、NP理论这几块。我会把每个模块里“必须掌握”和“了解即可”分开，你按自己的课时安排和考纲取舍。先有一张全局地图，再谈刷题，顺序不能反。

1. 复习先画地图：算法设计与分析期末的考点分布与主次排序

1.1 这门课的复习状态为什么容易“看了等于没看”

见过太多人复习算法课的方式：打开教材从头读到尾，读完第三章忘了第一章，合上书觉得“都会了”，一动手写题发现连递推式展开都算不明白。原因很简单——这门课和数据结构不一样，数据结构有具体的代码可以背，算法课考察的是“面对一个新问题，你能不能设计出正确且高效的解法”，这是能力题，不是记忆题。

所以复习策略必须反过来：先搞清楚每类题的固定套路，再刷题验证。比如动态规划大题，你只要掌握了“状态定义→转移方程→初始化→填表方向”这条线，不管题目换成背包还是最长公共子序列，都能套出答案。背题是最亏的复习方式，因为期末试卷里的原题比例通常很低，考察的是你迁移套路的能力。

1.2 各模块的考频和题型定位

我根据几所高校的算法期末卷和常见教材习题，把知识点模块做一个优先级排序。你复习时间不够的时候，按这个优先级取舍。

这个排序背后的逻辑很简单：期末卷子的区分度全靠“会设计算法”的大题拉开的，而设计题最稳定的出题方向就是动规和贪心。复杂度分析是小题的稳定考点，也是大题倒数第二问的常客。回溯和分支限界出现的频率稍微低一点，但一旦考到手推状态空间树，不会的人直接丢十几分。

1.3 试卷的时间分配建议

我考试时给自己定过一套时间分配，实测有效。假设卷面2小时，选择题/填空题控制在25分钟以内，这些题看的是概念的准确性，犹豫越久错得越多。递推方程求解这类计算题每道5-8分钟，重点检查主定理的应用条件。算法设计大题留足45分钟以上，宁可前面快速跳过不会的选择题，也要保证大题完整写出状态转移方程和伪代码。最后留5分钟检查复杂度公式是否写反。

2. 复杂度分析必练项：递推方程求解的套路与主定理使用陷阱

2.1 复杂度记号别只记符号含义，要会判断“紧界”

大O、大Ω、大Θ这三个记号是选择题的最爱，但很多同学只背了“上界、下界、紧界”这几个字，一放进具体表达式就懵。

我的记法是拿打车费类比：大O是“最贵不会超过多少钱”，大Ω是“司机再怎么绕也至少收这么多”，大Θ是“市场价稳定在一个区间，既不超过也不低于”。判断两个函数谁增长快，直接代n等于极大值看比值，比如n²和n log n的关系，代n=100000算一遍就彻底记住n²增长快得多。

考卷上常见的一组选择题是给一堆函数让你按渐近增长率排序，我整理了一个速记序列：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

注意O(n log n)和O(n√n)谁增长快这类边角比较很少考，但O(2ⁿ)和O(n!)的位置经常出现在选择题里，千万别把阶乘排到指数前面去——指数函数和阶乘相比，阶乘增长更快，因为阶乘是连乘到n，而指数只是连乘n个2。

2.2 递推方程求解的三种常规武器

期末考试递推方程的题目，九成可以用三种方法之一解决：代入法、递归树法、主定理。

代入法的核心是“先猜后证”，适合那种能凭直觉猜出答案的递推式。比如T(n)=T(n/2)+1，你猜T(n)=O(log n)，然后用数学归纳法证明。这里有个细节：证明时假设T(n/2)≤c·log(n/2)，代入右边得到c·log(n/2)+1 = c·log n - c + 1，要让这个式子≤c·log n，只要c≥1就行。很多同学归纳法证到一半就停，写成“显然成立”，在平时练习没问题，考试改卷会扣步骤分。

递归树法适合主定理搞不定的情况。以T(n)=2T(n/2)+n为例，展开后每一层的综合代价都是n，树共有log₂(n+1)层，总计n·log n。这个方法的好处是能直观看到总代价的增长来源，坏处是写起来费时间，考试时能认出主定时段就直接用主定理，实在认不出再展开画树。

2.3 主定理的三种情况，以及最容易翻车的细节

主定理说的是：T(n)=aT(n/b)+f(n)，其中a≥1，b>1，f(n)是渐近正的函数，那么：

• 情况1：f(n)=O(n^(log_b(a)-ε))，ε>0，则T(n)=Θ(n^log_b(a))。通俗讲就是f(n)增长比n^log_b(a)慢，复杂度被叶子节点主导。
• 情况2：f(n)=Θ(n^log_b(a))，则T(n)=Θ(n^log_b(a)·log n)。这是最常见的考法，比如T(n)=2T(n/2)+n，n^log₂2=n，f(n)=n，正好属于情况2，答案Θ(n log n)。
• 情况3：f(n)=Ω(n^(log_b(a)+ε))，ε>0，且a·f(n/b)≤c·f(n)，c<1，则T(n)=Θ(f(n))。此时复杂度被根节点主导。

翻车点有两个。第一个是：比较f(n)和n^log_b(a)要看多项式意义上的差距。如果f(n)=n log n，n^log_b(a)=n，你不能套情况3，因为f(n)/n^log_b(a)=log n，增长比任何n^ε都慢，这种情况主定理覆盖不了，得用其他方法。第二个翻车点是：忘了检查正则条件。情况3的a·f(n/b)≤c·f(n)如果不满足，结果不一定正确，考试里如果遇到了，老老实实展开递归树。

典型例题：

1. T(n)=2T(n/2)+n²，n^log₂2=n，f(n)=n²，f(n)增长比n快得多，且4·(n/2)²=n²≤c·n²（c=1满足正则条件），属于情况3，答案Θ(n²)。
2. T(n)=4T(n/2)+n，n^log₂4=n²，f(n)=n，属于情况1，答案Θ(n²)。

这两个例子一对比就发现：递归分解的“指数”a决定了树的宽度，a越大，叶子节点数量级越高，就算合并的代价很小，总复杂度也被叶子撑起来。

3. 三大设计策略的重头戏：分治、动态规划、贪心的题型模板

3.1 分治：先“分”后“合并”，合并步才是复杂度来源

分治的设计思路一句话：把一个大规模问题拆成若干个规模更小的同类子问题，分别解决后再把结果合并。递归出口通常是规模小到可以直接算。

期末最常考的分治题目有三个：归并排序、最大子段和、大整数乘法。

归并排序一定要会写递归式和分析过程。T(n)=2T(n/2)+O(n)，套主定理O(n log n)。值得注意的细节是归并的合并过程需要额外O(n)的辅助数组，所以空间复杂度是O(n)。

最大子段和是很多学校动规和分治都会出的题。分治思路把数组从中间切开，最大子段和要么完全在左边，要么完全在右边，要么跨过中间。前两种情况递归解决，第三种情况从中间往左右两边扩展找最大和，合并时比较三者。时间复杂度T(n)=2T(n/2)+O(n)=O(n log n)。这里想多说一句：如果题目限定数组里可以包含负数，一定要记得处理“整个数组全是负数”的边界情况，最大子段和应该是最大的那个负数，而不是0。

大整数乘法考察的是对复杂度的直观感受。普通乘法要把n位整数拆成两半，直接做4次乘法，T(n)=4T(n/2)+O(n)，主定理算出O(n²)。Karatsuba的优化思路是用3次乘法代替4次，T(n)=3T(n/2)+O(n)，算出来O(n^log₂3)≈O(n^1.585)。这个题如果作为解答题考，核心得分点是“为什么把ac+bd拆成(a+b)(c+d)-ac-bd可以省一次乘法”，一定要用自己的话把推导写清楚。

3.2 动态规划：期末大题的最稳定出题点

动态规划的大题，无论题目怎么变，答题都按四步走：定义状态→写转移方程→定初始化→定遍历顺序。这四个步骤写全了，就算最终答案有偏差，阅卷老师也能看到你的思路，给分不会太难看。

0-1背包是动态规划里最经典的题目。设dp[i][j]表示前i件物品装入容量为j的背包能获得的最大价值，转移方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)，其中wi是第i件物品重量，vi是价值。初始化dp[0][j]=0表示没有物品时价值为0。遍历顺序是先按物品遍历，再按容量遍历。如果用了滚动数组优化（只保留一维数组），内层循环必须倒序遍历，否则同一件物品会被重复选取，变成完全背包。这一条是期末选择题里的高频陷阱。

这里想补一个最近几年很多学校喜欢挖的变体：物品重量和价值不再按顺序给，而是交错出现，或者要求在O(1)空间完成。空间优化只影响代码实现，不影响状态定义和转移方程，你把基础版本写对了，优化是加分项。

**最长公共子序列（LCS）**的答题模板更固定。dp[i][j]表示字符串A前i个字符和字符串B前j个字符的LCS长度。转移方程分两种情况：

• 如果A[i]==B[j]，dp[i][j]=dp[i-1][j-1]+1；
• 否则，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

初始化dp[i][0]=dp[0][j]=0。填表时每个格子只依赖左边、上边和左上三个方向，所以遍历顺序是外层A内层B，顺序或倒序无所谓。如果题目要求输出具体子序列，还需要加一个记录表，标记每个格子是从哪个方向转移来的，答题时从表格右下角回溯即可。

矩阵连乘的转移方程和LCS长得像但含义完全不同。dp[i][j]表示从第i个矩阵到第j个矩阵全部相乘所需的最小标量乘法次数。转移方程dp[i][j] = min(dp[i][k] + dp[k+1][j] + p_{i-1}·p_k·p_j)，其中k在i到j-1之间枚举划分点。这个题容易错的地方在于遍历顺序不是简单的i从小到大：因为dp[i][j]依赖更大的区间dp[i][k]和dp[k+1][j]，必须先按区间长度从小到大计算。期末常考选择题“矩阵连乘应该怎么填表”，答案就是按长度递推。

3.3 贪心：先证明局部最优能推出全局最优

贪心算法在期末的考察分两个层面：一是给出一个场景，让你设计贪心策略并证明其正确性；二是让你分析某个策略是否可行。很多同学只学会了“设计”而没有学会“证明”，导致解答题丢分。

活动安排问题的标准贪心策略是：按结束时间从小到大排序，每次选择结束时间最早且和已选活动不冲突的活动。为什么按结束时间早排序而不是按持续时间短排序？因为结束时间早能给剩余活动留下更多时间空间，这是一个可以严格证明的贪心选择性质。证明思路是反证法：假设某个最优解中第一个活动不是结束时间最早的，把它换成结束时间最早的活动，新解不会比最优解差，从而说明贪心选择的正确性。这个证明逻辑在期末解答题就是得分点，我建议你把反证法的完整步骤写成自己能背下来的模板。

哈夫曼编码考察频率也很高，步骤是：统计字符出现频率，每次从最小堆中取出两个频率最小的节点合并，新节点的频率是它们之和，重新加入堆，直到只剩一个节点。这个题不光考“怎么做”，还经常考“编码长度怎么算”：从根到叶子的路径长度就是编码长度，叶子节点是字符，深度对应编码位数。有些学校会要求你手动画出哈夫曼树再给出每个字符的编码，画树的时候注意：如果有两个节点频率相同，合并顺序不影响总加权路径长度的最小值，但会影响具体编码，选择题遇到“唯一性”的描述，果断判断错误。

3.4 三者怎么选：一个容易上头但必须冷静的场景判断题

有些学校会把分治、动态规划、贪心放一起考判断题，给一个场景让你选合适方法。我的判断顺序是：

1. 子问题之间有没有重叠？如果没有重叠，分治优先；如果大量重叠，动态规划优先。
2. 当前选择会不会影响后续子问题的解空间？贪心要求“当前最优就是全局最优的一部分”，这个条件很难满足，大多数题都不满足，别一看能排序就选贪心。
3. 问题能不能通过“加上/不加当前元素”来递推？如果能，多半是动规。

举个例子：找零钱问题，如果硬币面额是1、5、11，找15块钱，贪心会选11+1+1+1+1（5个硬币），实际情况最优是5+5+5（3个硬币）。这就是典型看似能用贪心实则要用动态规划的场景。期末考这种“反直觉”题出现率不低。

4. 回溯与分支限界：解空间树、剪枝/限界函数的实战写法

4.1 回溯法：深度优先搜索剪枝，先画出解空间树

回溯法的本质是在解空间树上做带剪枝的深度优先搜索。期末最常考的三类问题：0-1背包、N皇后、图的m着色，其中0-1背包回溯和动规版本列在一起考察的概率很高。

先说解空间树的类型：0-1背包和子集和这类“在n个元素中选若干元素”的问题，解空间是子集树，节点数为2ⁿ；N皇后和旅行商这类“给n个元素排列”的问题，解空间是排列树，节点数为n!。考试简答经常问“某个问题的解空间规模是多少”，这两个数字直接背下来。

回溯框架的伪代码可以统一成：

void backtrack(当前层数 t): if t 超过最大层数: 记录/比较结果 return for 当前层的每个候选: if 剪枝条件满足: 剪枝 continue 更新状态 backtrack(t+1) 撤销状态

0-1背包的回溯解法要掌握两点：一是排序策略（按单位价值从大到小排），二是上界函数。上界函数通常是“当前价值加上剩余剩余物品全部装入后，按单位价值排序在上界内的最大价值”，如果上界小于当前已找到的最优解，直接剪枝。答题时别忘了说明：剪枝函数设计得越好，搜索空间越小，这也是回溯题的第二问经常考察的内容——“如何设计剪枝函数提高效率”。

N皇后问题是另一个高频考点。冲突判断条件是“同行、同列、同对角线”，用数组记录已放置皇后时，只需要判断列冲突和对角线冲突，行冲突因为逐行放置天然避免。对角线冲突的判断等价于|row1-row2|==|col1-col2|。这个题的剪枝条件是“当前位置与已有皇后冲突”，一旦冲突立即回溯，不需要计算上界。

期末如果要求你画出N皇后在n=4时的部分解空间树，一定要标清每层的分支和剪枝位置，画树的评分标准通常是结点、分支、剪枝标记三项各占一部分分。

4.2 分支限界法：广度优先加限界函数，重点在“界”

分支限界法和回溯法的本质区别在于搜索方式：回溯是深度优先，分支限界是广度优先或优先队列（最佳优先）。分支限界主要用于求解最优解，其核心是限界函数：先估算每个分支可能达到的目标函数值上/下界，超过当前最优界的节点直接丢弃，不继续扩展。

0-1背包的分支限界通常用优先队列实现：队列按节点的上界值排序，每次取出上界最大的节点扩展，扩展时计算左孩子（选第i件物品）和右孩子（不选）的上下界，如果某个孩子的上界不超过当前最优解，右孩子等不可能产生最优解的分支剪掉。

期末对这个部分的考察很少要求完整代码，更多是选择题里区分“回溯法和分支限界法的区别是什么”，答题要点是：回溯法用于搜索所有可行解或某个可行解，空间复杂度取决于解空间树的深度；分支限界法通常用于求最优解，空间复杂度更大，因为它要维护活节点表（队列或优先队列）。

4.3 回溯和分支限界的对比记忆

这个表格自己在草稿纸上默写一遍，比反复读教材更能形成记忆。注意有的学校会考“回溯法和分支限界法在0-1背包问题中的应用对比”，答题时先写相同点（都是解空间树上的搜索策略），再写上面表格的差异，基本可以拿满分。

5. NP理论、近似算法、概率算法的简答考点速记

5.1 P、NP、NPC、NP难四组概念别糊成一团

期末简答最喜欢考这四组概念的区别，我见过最多的错误答案是把NP写成“非多项式时间可解”，这完全错了。

• P类：存在多项式时间内解决的算法的问题。也就是能在O(n^k)时间内求出答案。
• NP类：存在多项式时间内验证“某个候选解是否为解”的问题。注意，NP的全称是Nondeterministic Polynomial，不是Non-Polynomial。能快速验证解，不代表能快速求解。
• NP完全（NPC）：既是NP问题，又属于NP难问题，所有NP问题都可以多项式时间归约到它。
• NP难（NP-Hard）：不要求本身是NP问题，只需要所有NP问题都能多项式时间归约到它。所以NPC一定是NP难，但NP难不一定是NP。

常见的NPC问题列举：SAT（布尔可满足性）、旅行商问题（TSP）、哈密顿回路、图着色、顶点覆盖、子集和。其中SAT是第一个被证明的NPC问题，期末考试如果考“第一个被证明的NPC问题是什么”，答案就是SAT，别答成背包问题。背包问题属于NP难，但需要在特定描述下才是NPC，简答题别拿它举例。

5.2 近似算法的近似比答题模板

近似算法出现的背景：对NPC问题，我们不知道多项式时间内能不能求出精确最优解，于是退一步求一个“足够接近最优解”的解，并给这个接近程度一个数学度量，这就是近似比。近似比ρ定义为近似解与最优解的比值（最大化问题和最小化问题的定义方向不同，考试常考最小化问题的形式，即近似解/最优解≤ρ）。

期末常考：用贪心算法求顶点覆盖问题，近似比为2。证明思路：贪心算法每次选择一条未被覆盖的边，并把它两个端点都加入覆盖集合。每次这样选边时，最优解至少要包含这条边的一个端点，所以贪心选入的点数不超过最优解的两倍。这个证明过程在教材里是完整段落，期末简答时按“选边→最优解必要条件→近似比”三段式写，逻辑清晰。

5.3 概率算法的四大家族

概率算法这个模块有些学校讲得深，有些学校只做了解要求，我按完整考点整理，你自己对照考纲取舍。

概率算法在期末出现的常见形式是选择/填空题，考点集中在四个类别：

• 数值随机算法：用随机采样估算数值，比如用蒙特卡洛法估算圆周率π，撒点落进四分之一圆的频率趋近π/4。
• 蒙特卡洛算法：执行时间确定，但结果可能出错，错误概率可以通过多次执行降低。
• 拉斯维加斯算法：结果一定正确，但执行时间是随机的，比如随机快速排序选主元。
• 舍伍德算法：用于消除算法的最坏情况，让算法在所有输入上的表现都比较均衡。

判断题“蒙特卡洛算法一定给出正确答案”是陷阱题，它的特点反而是“可能给错”，所以它适合允许出现小概率错误的场景。拉斯维加斯算法如果失败，可以重新运行，因为失败时算法会报告“我没找到解”，不会给出错误答案。

6. 冲刺阶段：高频易错点清单与答题评分规则

6.1 五个最容易丢分的细节

第一，复杂度记号混淆：算出一个算法最好情况是O(n)、最坏情况是O(n²)，不能写“算法复杂度是O(n)到O(n²)”，应该写“最好情况O(n)，最坏情况O(n²)”。复杂度是一个函数，不是一个区间。

第二，主定理应用时忘了检查a≥1且b>1：有些递推式形如T(n)=T(n/3)+T(2n/3)+O(n)，两个不同规模的子问题，主定理的a/b形式不适用，这时候递归树展开每层代价是O(n)，共有O(log n)层，结果O(n log n)。这类“变体递推”经常作为压轴小题出现。

第三，动规的初始化条件漏一个大边界：0-1背包的dp[0][j]和dp[i][0]都要初始化，LCS的dp[i][0]和dp[0][j]也要初始化，少一个，填表第一行/第一列全错。答题的时候先把表格的0行0列标出来，再写转移方程，阅卷老师一眼能看出你的严谨程度。

第四，贪心问题不写证明：很多同学设计出贪心策略就以为答题结束，但解答题要求的是“策略+正确性证明+复杂度分析”三件套，正确性证明用反证法或归纳法，写不长但必须有。没有证明的贪心题答案在改卷时最高只能拿一半分。

第五，回溯的剪枝函数和限界函数混为一谈：剪枝函数是约束函数，判断当前解是否满足题目约束；限界函数估算当前分支的目标函数上界，用于剪掉不可能产生更优解的分支。0-1背包回溯中这两个都出现，答题时分开写。

6.2 算法设计大题的答题模板

期末算法设计题的阅卷逻辑是按步骤给分。我强烈建议你按下面这个顺序答题，保证步骤清晰：

1. 明确子问题/状态定义：一句话说清楚dp[i][j]或者函数solve的输入输出含义。
2. 写出递推方程或关键逻辑：数学表达式优先。
3. 说明初始化和遍历顺序：动规题必须写，回溯题写递归出口。
4. 给出伪代码或关键代码片段：不用写完整可编译代码，但核心逻辑要完整。
5. 分析时间/空间复杂度：写O(n²)这类记号，加一句说明来源。

我见过学弟学妹吃大亏的场景：动规大题状态定义对了，转移方程对了，结果遍历顺序写错，整张表填出来是错误的答案，这个大题就从“接近满分”滑到“勉强给一半”。考试时答完题花30秒自查一遍遍历顺序，非常值得。

6.3 考前一周的实操安排

最后一星期不建议再啃新题。把教材或老师PPT里所有例题的递推方程自己抄一遍，然后每个题口算一遍复杂度。接着刷3-5套历年真题或课后典型题，重点练“限时写出完整答案”的能力。临考前一夜，把主定理三种情况、0-1背包的转移方程、贪心三件套答题模板、N皇后的冲突判断条件再过一遍，这些是高频保分点。

这门课复习的本质是练“条件反射”——看到“最大价值”，反射出dp和背包；看到“两字符串最长公共”，反射出LCS的转移方程；看到“最小生成树”“最早结束时间”，反射出排序加贪心。你要的不是看懂每一个证明细节，而是把那些最核心的模型刻进脑子里，考场上能稳定输出。

我从自己带过的学生复习数据看，把本文提到的每道经典题独立写一遍、不看书自己推导出结果的同学，期末成绩普遍在85分以上。这门课不考天赋，考熟练度。刷就完了。