《算法设计与分析》期末复习完全手册（直接使用版）

《算法设计与分析》期末复习完全手册（直接使用版）第一部分：考试题型与分值分布（通用）题型题量分值主要考查范围策略选择题15-20题20-30分算法复杂度、分治、DP、贪心、回溯基本概念、NP理论辨析概念，牢记特征与反例填空题10-15题10-15分递推式求解、最优子结构性质、算法设计步骤熟记主定理及经典算法复杂度判断题10题10分算法性质辨析注意概念精确性简答题3-4题15-20分算法思想、方法比较、NP完全问题举例分点作答，辅以实例算法设计题2-3题20-30分分治、DP、贪心、回溯设计，证明正确性，分析复杂度掌握经典问题模板证明/分析题1-2题10-15分算法正确性、最优子结构、复杂度递推、NP归约逻辑严密，层次清楚第二部分：算法基础知识速查2.1算法定义与特性特性含义有穷性执行有限步后结束，每一步在有穷时间内完成确定性每步指令明确，无歧义可行性每步操作都可执行输入有零个或多个输入输出至少有一个输出2.2算法复杂度分析时间复杂度：算法执行时间随问题规模n的增长趋势。常用渐近上界O、下界Ω和紧确界Θ。空间复杂度：算法所需额外存储空间。递归算法分析：解递归式常考：迭代展开法（递推树）主定理（MasterTheorem）：对T(n)=aT(n/b)+f(n)若f(n)=O(nlogba-ε)，则T(n)=Θ(nlogba)若f(n)=Θ(nlogba)，则T(n)=Θ(nlogbalogn)若f(n)=Ω(nlogba+ε)且满足正规性条件，则T(n)=Θ(f(n))第三部分：分治法（DivideandConquer）3.1基本步骤分解：将原问题划分为若干个规模较小、相互独立的子问题。求解：递归求解子问题，直至可直接求解。合并：将子问题的解合并为原问题的解。3.2经典分治算法问题时间复杂度关键点二分搜索O(logn)仅适用于有序表归并排序O(nlogn)先分后合，需O(n)辅助空间，稳定快速排序平均O(nlogn)，最坏O(n²)划分后递归，枢轴选择影响效率，不稳定大整数乘法O(nlog23)≈O(n¹·⁵⁹)Karatsuba：三次乘法代替四次Strassen矩阵乘法O(nlog27)≈O(n²·⁸¹)7次乘法代替8次最近点对O(nlogn)跨越中线的处理是关键最大子数组O(nlogn)或O(n)分治：跨越中点的子数组需特殊处理第四部分：动态规划（DP）4.1基本要素要素说明最优子结构问题的最优解包含其子问题的最优解重叠子问题递归求解过程中重复计算相同的子问题无后效性某阶段状态一旦确定，之后决策不受之前影响4.2解题步骤刻画最优解的结构特征。递归定义最优解的值（状态转移方程）。计算最优值（自底向上或带备忘录的递归）。构造最优解（通常需记录路径）。4.3经典DP问题问题状态转移/核心复杂度矩阵连乘dpHYPERLINKi=min(dpHYPERLINKi+dpHYPERLINKk+1+pi-1pkpj)O(n³)最长公共子序列(LCS)xi=yj：dpHYPERLINKi=dpHYPERLINKi-1+1；否则max(dpHYPERLINKi-1,dpHYPERLINKi)O(mn)0-1背包dpHYPERLINKi=max(dpHYPERLINKi-1,dpHYPERLINKi-1+vi)O(nW)最长递增子序列(LIS)dp[i]=max(dp[j]+1)forj<ianda[j]<a[i]O(n²)或O(nlogn)编辑距离类似LCSO(mn)最优二叉搜索树dpHYPERLINKi类似矩阵连乘O(n³)石子合并/区间DP区间划分O(n³)Floyd最短路径dpHYPERLINKi=min(dpHYPERLINKi,dpHYPERLINKi+dpHYPERLINKk)O(n³)第五部分：贪心法（Greedy）5.1基本要素要素说明贪心选择性质全局最优可通过一系列局部最优（贪心选择）达到最优子结构问题的最优解包含子问题的最优解5.2经典贪心算法问题贪心策略复杂度活动安排按结束时间递增顺序选择O(nlogn)背包问题（可分割）按单位价值降序选取O(nlogn)哈夫曼编码每次选权值最小的两棵树合并O(nlogn)最小生成树Prim每次选连接已选顶点集的最小权边O(n²)或O(elogn)最小生成树Kruskal每次选不构成回路的最小权边O(eloge)Dijkstra最短路径每次选当前距离最小的未标记顶点O(n²)找零问题先选最大面值（要求硬币系统规范）O(n)5.3贪心正确性证明方法数学归纳法交换论证法：将任意最优解逐步转换为贪心解且不降低目标值剪贴法：证明贪心选择仍包含最优解第六部分：回溯法与分支限界法6.1回溯法按深度优先搜索解空间树。用约束函数剪去不满足约束的子树，用限界函数剪去不能得到最优解的子树。典型解空间树：子集树O(2ⁿ)、排列树O(n!)。经典问题：n皇后、图的m着色、旅行商问题(TSP)、0-1背包、装载问题。6.2分支限界法按广度优先或最小耗费优先搜索解空间树。每个活结点计算一个下界/上界（限界），使用优先队列，先扩展限界最优的结点。通常用于求最优解。6.3回溯法与分支限界法对比区别回溯法分支限界法搜索方式深度优先广度优先/优先队列求解目标所有解或一个解最优解剪枝方式约束函数+限界函数限界函数（下界/上界）存储结构栈（递归）队列/优先队列第七部分：概率分析与随机算法概率分析：假定输入服从某种概率分布，分析算法期望时间。例：线性查找平均查找长度。随机算法：内部使用随机数，期望运行时间与输入排列无关。随机快速排序：随机选择枢轴，期望时间O(nlogn)。随机选择算法：期望线性时间找第k小元素。第八部分：计算复杂性理论与NP完全性8.1P、NP、NP完全、NP难类含义举例P确定性图灵机多项式时间可解排序、最短路径NP非确定性图灵机多项式时间可解；或确定性图灵机多项式时间可验证SAT、旅行商决策问题NP完全(NPC)属于NP，且所有NP问题可多项式归约到它SAT、3-CNF-SAT、分团问题NP难(NP-Hard)所有NP问题可多项式归约到它，自身不一定在NP停机问题、TSP优化版8.2多项式归约A≤pB：存在多项式时间算法将A实例转化为B实例，A有解⇔B有解。若B∈P，则A∈P。8.3经典NPC问题SAT、3-SAT、分团问题（Clique）、顶点覆盖（VertexCover）、哈密顿回路、旅行商决策问题、子集和问题。第九部分：高频选择题题库（40题）模块一：算法基础与复杂度题号题目ABCD答案1算法必须具备的特性不包括有穷性确定性美观性可行性C2渐近符号O表示精确增长上界下界紧确界B3T(n)=2T(n/2)+n的解为O(n)O(nlogn)O(n²)O(logn)B4T(n)=T(n-1)+n的解为O(n)O(logn)O(n²)O(nlogn)C模块二：分治法题号题目ABCD答案5归并排序空间复杂度O(1)O(logn)O(n)O(nlogn)C6快排最坏情况时间复杂度O(n)O(nlogn)O(n²)O(1)C7二分搜索要求表为无序顺序有序顺序链表哈希B8Strassen矩阵乘法减少乘法次数原理分块递归7次代替8次迭代贪心DPA模块三：动态规划题号题目ABCD答案9DP必须具备的性质不包括最优子结构重叠子问题贪心选择性质子问题独立C10LCS问题的时间复杂度是O(n)O(mn)O(n²)O(m+n)B110-1背包动态规划时间复杂度O(nW)O(n²)O(2ⁿ)O(nlogn)A12Floyd算法用到了分治贪心动态规划回溯C模块四：贪心法题号题目ABCD答案13贪心法基本要素不包括最优子结构重叠子问题贪心选择性质—B14活动安排问题的贪心标准是开始时间递增结束时间递增活动时长递增单位价值B15哈夫曼编码用到的数据结构是栈队列优先队列图C16Dijkstra算法属于分治贪心DP回溯B模块五：回溯与分支限界题号题目ABCD答案17n皇后问题用回溯法，解空间树是子集树排列树满二叉树图B18回溯法剪枝不满足约束用限界函数约束函数评估函数代价函数B19分支限界法通常使用的数据结构是栈队列优先队列数组C20回溯法求解0-1背包，通常用排列树子集树哈夫曼树平衡树B模块六：NP理论题号题目ABCD答案21P类问题指指数时间可解多项式时间可解多项式时间可验证不可解B22NP类问题指非多项式可解多项式时间可验证多项式时间可解指数可解B23以下属于NP完全问题的是排序Dijkstra旅行商决策问题最小生成树C24如果所有NP问题可归约到一个问题，它属于PNPNP难以上皆可能C模块七：综合题号题目ABCD答案25归并排序体现的算法思想贪心DP分治回溯C26能获得全局最优解的一定是贪心回溯都不一定以上都不对C27LIS最优算法复杂度O(n)O(n²)O(nlogn)O(2ⁿ)C28矩阵连乘DP时间复杂度O(n²)O(n³)O(n)O(2ⁿ)B290-1背包不可用贪心因为缺少最优子结构贪心选择性质重叠子问题无后效性B30随机快速排序期望时间复杂度O(n)O(nlogn)O(n²)O(logn)B31Kruskal算法判断回路常用栈并查集优先队列链表B32T(n)=T(n/3)+T(2n/3)+n时间复杂度接近O(n)O(nlogn)O(n²)O(logn)B33回溯法解0-1背包，限界通常取剩余物品总价值贪心法上界简单平均值最小值B34哪个不是算法设计基本方法动态规划回溯机器学习分治C35T(n)=2T(n/2)+nlogn，n=1时T(n)=1，复杂度O(n)O(nlogn)O(nlog²n)O(n²)C36快速排序最坏情况的改进方法随机选枢轴三数取中两者均是不可改进C37最优子结构性质是哪种算法的基础贪心DP贪心和DP回溯C38关于NP完全问题正确的是NP难问题都在NP中所有NPC问题都可多项式相互归约P=NP已被证明所有NP问题都在P中B39回溯法遍历排列树的复杂度O(2ⁿ)O(n!)O(n²)O(n)B40分支限界法活结点表优先级按深度结点序号限界值（下界/上界）随机C第十部分：填空题高频考点（直接背诵）序号题目答案1算法的五个特性：有穷性、确定性、可行性、输入、____。输出2T(n)=3T(n/2)+n的主定理结果为____。Θ(nlog23)3分治法三个步骤：分解、____、合并。递归求解4归并排序的时间复杂度为____。O(nlogn)5快速排序最坏时间复杂度为____。O(n²)6DP两大要素：最优子结构和____。重叠子问题70-1背包问题动态规划时间复杂度为____。O(nW)8LCS递推：若xi=yj，则dpHYPERLINKi=dpHYPERLINKi-1____1。+9贪心算法的两个基本要素：贪心选择性质和____。最优子结构10活动安排问题中贪心选择按____时间非递减排序。结束11哈夫曼树构建中用到的数据结构是____。优先队列（最小堆）12Dijkstra算法求单源最短路径，权值必须____。非负13回溯法按____优先搜索解空间树。深度14分支限界法通常借助____队列实现。优先15n皇后问题解空间为____树。排列16P类问题指可用____时间求解的问题。多项式17NP类问题指可用____时间验证的问题。多项式18第一个被证明为NP完全的问题是____（Cook定理）。SAT（布尔可满足性问题）19如果存在多项式算法解决某个NPC问题，则P____NP。=20随机快速排序的期望时间复杂度为____。O(nlogn)第十一部分：判断题速记（15题）序号题目答案1所有递归算法都可以转化为非递归算法。对（用栈模拟）2O(1)表示算法执行时间为常数。对3快速排序在任何情况下都是最快的排序算法。错（最坏O(n²)）4分治法分解的子问题必须相互独立。对5动态规划与分治法的主要区别是子问题是否重叠。对6所有问题都能用贪心算法求得最优解。错7哈夫曼编码是一种最优前缀码。对8Dijkstra算法可以处理负权边。错9回溯法通过限界函数和约束函数剪枝。对10分支限界法只能采用广度优先策略。错（常用优先队列）11P⊆NP。对12如果一个问题属于NP，那它一定是NP完全的。错13旅行商优化问题属于NP完全问题。错（NP难，决策版是NPC）14快速排序的枢轴选择会影响算法效率。对15合并排序是原地排序算法。错（需要O(n)辅助空间）第十二部分：简答题高频考点1.简述分治法与动态规划的区别。分治法：子问题相互独立，无重复计算，自顶向下递归求解后合并。动态规划：子问题重叠，保存已解子问题答案避免重复，自底向上或带备忘录计算。2.简述贪心算法的基本要素及证明方法。要素：贪心选择性质、最优子结构。证明方法：数学归纳法、交换论证、剪贴法。3.简述回溯法与分支限界法的异同。同：均在解空间树搜索，都使用剪枝函数。异：回溯法深度优先，求所有解或一个解；分支限界法广度或最小耗费优先，求最优解，通常用优先队列存储活结点。4.解释P、NP、NP完全的含义并举例。P：多项式时间可解，如排序。NP：多项式时间可验证，如哈密顿回路的存在性验证。NP完全：属于NP且所有NP问题可多项式归约到它，如SAT。5.证明0-1背包问题具有最优子结构性质。设(y1,…,yn)是容量W下的最优解，则(y2,…,yn)是子问题（容量W-w1y1）的最优解。否则用更优子解替换可得到整体更优，矛盾。第十三部分：算法设计题示例例1：二分搜索（分治）defbinary_search(arr,l,r,x):

ifr>=l:

mid=l+(r-l)//2

ifarr[mid]==x:returnmid

elifarr[mid]>x:returnbinary_search(arr,l,mid-1,x)

else:returnbinary_search(arr,mid+1,r,x)

return-1例2：归并排序（分治）defmerge_sort(arr):

iflen(arr)<=1:returnarr

mid=len(arr)//2

left=merge_sort(arr[:mid])

right=merge_sort(arr[mid:])

returnmerge(left,right)

defmerge(left,right):

res=[]

i=j=0

whilei<len(left)andj<len(right):

ifleft[i]<=right[j]:res.append(left[i]);i+=1

else:res.append(right[j]);j+=1

res.extend(left[i:]);res.extend(right[j:])

returnres例3：0-1背包（动态规划）defknapsack(W,wt,val,n):

dp=[[0]*(W+1)for_inrange(n+1)]

foriinrange(1,n+1):

forwinrange(W+1):

ifwt[i-1]<=w:

dp[i][w]=max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1])

else:

dp[i][w]=dp[i-1][w]

returndp[n][W]例4：活动安排（贪心）defactivity_selection(start,finish):

acts=sorted(zip(start,finish),key=lambdax:x[1])

selected=[acts[0]]

last_f=acts[0][1]

fors,finacts[1:]:

ifs>=last_f:

selected.append((s,f))

last_f=f

returnselected例5：N皇后（回溯）defsolve_n_queens(n):

defis_safe(board,row,col):

foriinrange(row):

ifboard[i]==colorabs(board[i]-col)==row-i:

returnFalse

returnTrue

defbacktrack(row):

ifrow==n:

res.append(board[:])

return

forcolinrange(n):

ifis_safe(board,row,col):

board[row]=col

backtrack(row+1)

board=[-1]*n

res=