《算法设计与分析》第一学期期末试卷A (精选04)大学生期末考试复习平台前往平台难度⭐考点#渐近复杂度#O记号#Omega记号#Theta记号#极限比较:::: details 学习锦囊 相关公式与知识点定义若存在 (c0,n_0)当 (n\ge n_0) 时(f(n)\ge c,g(n))则 (f(n)\Omega(g(n)))常用判别若 (\lim_{n\to\infty} f(n)/g(n)\infty)则 (f(n)\Omega(g(n)))。::: warning 易错点将( \log^2 n) 误当作(2\log n)注意这里是平方看到对数就直接下结论(O(\log n))忽略平方导致增长更快。::::::::::: details 举一反三比较 (f(n)\log_2 n) (g(n)\sqrt{\log_2 n}) 的渐近关系。::: details 查看练习答案与解析答案(\log_2 n\Omega(\sqrt{\log_2 n}))。解析lim n → ∞ log 2 n log 2 n lim n → ∞ log 2 n ∞ \lim_{n\to\infty}\frac{\log_2 n}{\sqrt{\log_2 n}} \lim_{n\to\infty}\sqrt{\log_2 n} \inftyn→∞limlog2nlog2nn→∞limlog2n∞故 (f\Omega(g))。:::比较 (f(n)\log_2^3 n) (g(n)n^\epsilon)其中(\epsilon0) 为常数。::: details 查看练习答案与解析答案(\log_2^3 no(n^\epsilon))即 (g(n)\Omega(f(n)))。解析关键结论任意固定次幂对数都比任意正幂的多项式增长慢可用极限。(\lim_{n\to\infty}\log^k n / n^\epsilon 0)(k) 为常数证明。::::::::::::2. 给出汉诺塔递归算法分析其时间复杂度void Hanoi(int n,char x, char y, char z) { if(n1) printf(将盘片%d从%c搬到%c\n,n,x,z); else { Hanoi(n-1,x,z,y); printf(将盘片%d从%c搬到%c\n,n,x,z); Hanoi(n-1,y,x,z); } }::::: details 查看答案与解析答案时间复杂度(O(2^n))更精确执行打印次数为 (2^n-1)。解析步骤完整*建立递推案设执行时间(T(n))(n1) 时只执行一次打印(T(1)\Theta(1))(n1) 时算法包含两次规模(n-1) 的递归调用(O(1)) 次常数操作一次打印T ( n ) 2 T ( n − 1 ) Θ ( 1 ) . T(n)2T(n-1)\Theta(1).T(n)2T(n−1)Θ(1).展开递推T ( n ) 2 T ( n − 1 ) 1 2 ( 2 T ( n − 2 ) 1 ) 1 2 2 T ( n − 2 ) 2 1 2 3 T ( n − 3 ) 2 2 2 1 ⋮ 2 n − 1 T ( 1 ) ( 2 n − 2 2 n − 3 ⋯ 2 1 ) 2 n − 1 Θ ( 1 ) ( 2 n − 1 − 1 ) Θ ( 2 n ) . \begin{aligned} T(n) 2T(n-1)1\\ 2\bigl(2T(n-2)1\bigr)1 2^2T(n-2)21\\ 2^3T(n-3)2^221\\ \;\;\vdots\\ 2^{n-1}T(1)(2^{n-2}2^{n-3}\cdots21) \\ 2^{n-1}\Theta(1) (2^{n-1}-1) \\ \Theta(2^n). \end{aligned}T(n)2T(n−1)12(2T(n−2)1)122T(n−2)2123T(n−3)2221⋮2n−1T(1)(2n−22n−3⋯21)2n−1Θ(1)(2n−1−1)Θ(2n).因此时间复杂度为 (O(2^n))方法总结遇到“两个子问题规模都为 (n-1) 常数工作量”常见形式 (T(n)2T(n-1)O(1))直接展开或用主定递推求和即可。难度⭐考点#递归#递推式#时间复杂度#汉诺塔:::: details 学习锦囊 相关公式与知识点经典递推(T(n)aT(n-1)b\Rightarrow T(n)\Theta(a^n))当 (a1) (b\Theta(1))汉诺塔移动次数(M(1)1)(M(n)2M(n-1)1\Rightarrow M(n)2^n-1)::: tip 思路分析先看“递归调用次数与规模”决定指数底数再看“非递归部分”是常数还是线性等。::::::::::: details 举一反三若递推(T(n)3T(n-1)2)求 (T(n)) 的渐近复杂度::: details 查看练习答案与解析答案(\Theta(3^n))。解析展开可得 (T(n)3{n-1}T(1)2(3{n-2} \cdots 1)\Theta(3^n)):::若递推(T(n)2T(n-1)n)求 (T(n)) 的渐近复杂度::: details 查看练习答案与解析答案(\Theta(2^n))。解析要点展开后出(\sum_{k1}{n-1}2{n-1-k}\cdot k)该和为 (\Theta(2^n))::::::::::::3. 顺序查找算法如下回答平均复杂度问题在长度为 (n) 的数a[0..n-1]中顺序查找值为 (x) 的元素找到返回 1否则返0int Find(double a[], int n, double x) { int i 0; while (i n) { if (a[i] x) break; i; } if (i n) return 1; else return 0; }回答案案在“成功查找且每个位置等概率”的条件下最优最优平均时间复杂度分别是什么若 (x) 在数组中出现的概率为 (q)求算法的平均时间复杂度期望比较次数。::::: details 查看答案与解析答案与最好(O(1))最坏(O(n))平均成功且等概率(O(n))且成功时的期望比较次数(\frac{n1}{2})若 (x) 在数组中概率(q)则期望比较次数E ( n ) q ⋅ n 1 2 ( 1 − q ) ⋅ n , E(n)q\cdot\frac{n1}{2}(1-q)\cdot n,E(n)q⋅2n1(1−q)⋅n,因此平均时间复杂度为 (O(n))。解析步骤完整把“数组元素与 (x) 的一次比较”作为基本操作记比较次数为 (C)成功查找且等概*最好情案(a[0]x)只需比较 1 次(C_{\min}1\Rightarrow O(1))*最坏情况成功案(a[n-1]x)比较(n) 次(C_{\max}n\Rightarrow O(n))。平均情况成功且等概率若 (x) 出现在位(i)(0\le i\le n-1)则比较次数为 (i1)且P ( i ) 1 n . P(i)\frac{1}{n}.P(i)n1.因此E [ C ∣ 成功 ] ∑ i 0 n − 1 1 n ( i 1 ) 1 n ⋅ n ( n 1 ) 2 n 1 2 Θ ( n ) . E[C\mid \text{成功}] \sum_{i0}^{n-1}\frac{1}{n}(i1) \frac{1}{n}\cdot\frac{n(n1)}{2} \frac{n1}{2} \Theta(n).E[C∣成功]i0∑n−1n1(i1)n1⋅2n(n1)2n1Θ(n).出现概率为 (q) 的一般平将“成功查找”和“不成功查找”合并计算期望成功查找概率(q)且默认成功位置等概率成功时的期望比较次数为 (\frac{n1}{2})不成功查找概率为 (1-q)循环会(i) 0 比较(n-1)比较次数为 (n)所以总期望为E ( n ) q ⋅ n 1 2 ( 1 − q ) ⋅ n . E(n)q\cdot\frac{n1}{2}(1-q)\cdot n.E(n)q⋅2n1(1−q)⋅n.(q\frac12) 时E ( n ) 1 2 ⋅ n 1 2 1 2 ⋅ n 3 n 1 4 ≈ 3 4 n . E(n)\frac12\cdot\frac{n1}{2}\frac12\cdot n\frac{3n1}{4}\approx\frac{3}{4}n.E(n)21⋅2n121⋅n43n1≈43n.方法总结平均复杂度本质是“期望基本操作次数”先写清每种情形的代价再按概率加权求和。难度⭐考点#顺序查找#平均时间复杂度#期望#概率模型:::: details 学习锦囊 相关公式与知识点等差数列求和(\sum_{k1}^{n}k\frac{n(n1)}{2})。平均比较次数的写法(E\sum p_i\cdot c_i)。::: warning 易错点把“不成功查找”当(n1) 次比较本代码中是比较数组元素次数因此(n) 次若包in的判断则另计平均“成功查找”与“总体含不成功平均”混为一谈。::::::::::: details 举一反三若成功位置不等概率(P(i)\frac{2(i1)}{n(n1)})越靠后概率越大求成功时的期望比较次数。::: details 查看练习答案与解析答案(E\frac{2}{n(n1)}\sum_{i0}{n-1}(i1)2\frac{2}{n(n1)}\cdot\frac{n(n1)(2n1)}{6}\frac{2n1}{3}\Theta(n))。解析将 (ki1)用平方和公式(\sum_{k1}{n}k2\frac{n(n1)(2n1)}{6})式:::设数组已排序用二分查找比较次数的最优最优平均复杂度分别是什么(n) 为规模。::: details 查看练习答案与解析答案最优(O(1))最优(O(\log n))平与(O(\log n))与解析要点每次比较后把区间规模减半比较次数约为 (\lfloor \log_2 n \rfloor 1)::::::::::::二、简答题每小题 5 分20 分1. 算法设计的基本步骤::::: details 查看答案与解析答案要点问题分析明确目标输出、约束条件输入、边界情况与评价指标*选择数据结构与设计策案根据问题特性选择合适的数据表示与策略迭代/分治/动态规回溯/贪心等描述算法给出清晰的步骤描述伪流程结构化语言并定义关键变量与过程*正确性证案论证算法对所有合法输入都能得到正确输出不变式、归纳、最优子结构等复杂度分析与优化共析时间空间复杂度必要时改进与权衡。难度⭐考点#算法设计流程#正确性证明#复杂度分析:::: details 学习锦囊 相关公式与知识点常用正确性证明。循环不变式、数学归纳法、反证法复杂度评价渐近上界 (O(\cdot))、下(\Omega(\cdot))、紧。(\Theta(\cdot))。:::::::: details 举一反三简述“算法分析”通常包括哪些指标。::: details 查看练习答案与解析答案主要包括时间复杂度、空间复杂度在工程中也会考虑常数因子、缓IO、可并行性与稳定性等与解析理论课以渐近复杂度为主实际实现需结合平台与数据分布可::::::::::::2. 能用递归解决的问题应满足哪些基本条件。::::: details 查看答案与解析答案要点可分解为规模更小的同类子问题原问题可转化为一个或多个结构相同、规模更小的子问题*递归必须有终止条件基本情形案存在可直接求解的最小规模输入且能被触达态*规模严格缩小且调用次数有案每次递归都使规模朝终止条件推进否则会无限递归。难度⭐考点#递归#递归终止条件#递归分解:::: details 学习锦囊 相关公式与知识点递归通常对应递推式用于复杂度分析(T(n)aT(n/b)f(n)) 。(T(n)aT(n-1)f(n))。:::::::: details 举一反三为什么“有终止条件”还不够还需要“规模严格缩小”::: details 查看练习答案与解析答案如果每次递归不缩小规模即使写了终止条件也可能永远到不了终止状态例如不断对同一规模调用自己仍会无限递归与解析终止条件是“存在”规模缩小是“可达”::::::::::::3. 简述动态规划与分治法的异同。::::: details 查看答案与解析答案要点*相同案都把原问题分解为子问题再由子问题解组合得到原问题解都依赖“最优子结构/可组合性”**不同**分治案子问题通常相互独立不重递归求解再合并结果如归并排序动态规案子问题通常重叠*用“记忆化/表格法”复用子问题结果避免重复计算常配合“阶状态转移”建模。难度⭐考点#动态规划#分治#重叠子问题#最优子结构:::: details 学习锦囊 相关公式与知识点DP 三要素状态定义、状态转移方程、边界与遍历顺序“重叠子问题”是 DP 相比分治的关键差异点:::::::: details 举一反三举一个“分治适用DP 不占优势”的例子并说明原因。::: details 查看练习答案与解析答案归并排序与解析子问题互不重叠分治每个子问题只算一次DP 的缓存并不会减少工作量。:::举一个“DP 明显优于纯分治”的例子并说明原因。::: details 查看练习答案与解析答案斐波那契数列与解析(F(n)F(n-1)F(n-2)) 子问题大量重叠DP/记忆化能把指数级降为线性::::::::::::4. 简述贪心法适用问题应具有的性质。::::: details 查看答案与解析答案要点贪心选择性质存在一种局部最优选择策略使得每一步做出的局部最优选择最终能导向全局最优解析最优子结构性质问题的最优解包含子问题的最优解做出一次选择后剩余部分仍是同类规模更小的最优化问题。难度⭐考点#贪心#贪心选择性质#最优子结构:::: details 学习锦囊 相关公式与知识点贪心正确性证明常见套路交换论证exchange argument、归纳证明、反证。:::::::: details 举一反三说明“最优子结构”与“贪心选择性质”哪个更强为什么::: details 查看练习答案与解析答案贪心选择性质更强与解析很子DP 问题有最优子结构但不具备贪心选择性质无法用每步局部最优直接得到全局最优0/1 背包::::::::::::
