当前位置：首页 > news >正文

《算法设计与分析》第一学期期末试卷A (精选04)

news 2026/5/28 14:45:59

《算法设计与分析》第一学期期末试卷A (精选04)

大学生期末考试复习平台前往平台

难度：⭐
考点：#渐近复杂度#O记号#Omega记号#Theta记号#极限比较

:::: details 💡 学习锦囊
📖 相关公式与知识点

定义：若存在 (c>0,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→∞limlog2nlog2n=n→∞limlog2n=+∞
故 (f=\Omega(g))。
:::
比较 (f(n)=\log_2^3 n) ：(g(n)=n^\epsilon)（其中(\epsilon>0) 为常数）。
::: details 查看练习答案与解析
答案：(\log_2^3 n=o(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(n==1) 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))：
- ：(n=1) 时，只执行一次打印，(T(1)=\Theta(1))：
- ：(n>1) 时，算法包含两次规模：(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)+2+1\\ &= 2^3T(n-3)+2^2+2+1\\ &\;\;\vdots\\ &= 2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1) \\ &= 2^{n-1}\Theta(1) + (2^{n-1}-1) \\ &= \Theta(2^n). \end{aligned}T(n)=2T(n−1)+1=2(2T(n−2)+1)+1=22T(n−2)+2+1=23T(n−3)+22+2+1⋮=2n−1T(1)+(2n−2+2n−3+⋯+2+1)=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))（当 (a>1) （(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_{k=1}^{n-1}2{n-1-k}\cdot k)，该和为 (\Theta(2^n))，
:::
::::

:::::

3. 顺序查找算法如下，回答平均复杂度问题：

在长度为 (n) 的数：a[0..n-1]中顺序查找值为 (x) 的元素，找到返回 1，否则返：0：

int 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{n+1}{2})（
（）若 (x) 在数组中概率）(q)，则期望比较次数：

E ( n ) = q ⋅ n + 1 2 + ( 1 − q ) ⋅ n , E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n,E(n)=q⋅2n+1+(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)），则比较次数为 (i+1)，且

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_{i=0}^{n-1}\frac{1}{n}(i+1) =\frac{1}{n}\cdot\frac{n(n+1)}{2} =\frac{n+1}{2} =\Theta(n).E[C∣成功]=i=0∑n−1n1(i+1)=n1⋅2n(n+1)=2n+1=Θ(n).

（）出现概率为 (q) 的一般平：

将“成功查找”和“不成功查找”合并计算期望：

成功查找概率）(q)，且（默认成功位置等概率）成功时的期望比较次数为 (\frac{n+1}{2})，
不成功查找概率为 (1-q)，循环会：(i) ：0 比较：(n-1)，比较次数为 (n)，

所以总期望为

E ( n ) = q ⋅ n + 1 2 + ( 1 − q ) ⋅ n . E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n.E(n)=q⋅2n+1+(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{n+1}{2}+\frac12\cdot n=\frac{3n+1}{4}\approx\frac{3}{4}n.E(n)=21⋅2n+1+21⋅n=43n+1≈43n.

方法总结：平均复杂度本质是“期望基本操作次数”；先写清每种情形的代价，再按概率加权求和。

难度：⭐：
考点：#顺序查找#平均时间复杂度#期望#概率模型

:::: details 💡 学习锦囊
📖 相关公式与知识点

等差数列求和：(\sum_{k=1}^{n}k=\frac{n(n+1)}{2})。
平均比较次数的写法：(E=\sum p_i\cdot c_i)。

::: warning 易错点

把“不成功查找”当：(n+1) 次比较（本代码中是比较数组元素次数，因此：(n) 次；若包：i<n的判断则另计）：
平均“成功查找”与“总体（含不成功）平均”混为一谈。
:::
::::

:::: details 🔄 举一反三

若成功位置不等概率：(P(i)=\frac{2(i+1)}{n(n+1)})（越靠后概率越大），求成功时的期望比较次数。
::: details 查看练习答案与解析
答案：(E=\frac{2}{n(n+1)}\sum_{i=0}^{n-1}(i+1)2=\frac{2}{n(n+1)}\cdot\frac{n(n+1)(2n+1)}{6}=\frac{2n+1}{3}=\Theta(n))。
解析：将 (k=i+1)，用平方和公式(\sum_{k=1}^{n}k2=\frac{n(n+1)(2n+1)}{6})式
:::
设数组已排序，用二分查找，比较次数的最优最优平均复杂度分别是什么（）(n) 为规模）。
::: details 查看练习答案与解析
答案：最优(O(1))，最优(O(\log n))，平与(O(\log n))与
解析（要点）：每次比较后把区间规模减半，比较次数约为 (\lfloor \log_2 n \rfloor + 1)，
:::
::::

:::::

二、简答题（每小题 5 分，：20 分）

《算法设计与分析》第一学期期末试卷A (精选04)

大学生期末考试复习平台前往平台

2. 给出汉诺塔递归算法，分析其时间复杂度：

3. 顺序查找算法如下，回答平均复杂度问题：

二、简答题（每小题 5 分，：20 分）

1. 算法设计的基本步骤？

2. 能用递归解决的问题应满足哪些基本条件。

3. 简述动态规划与分治法的异同。

4. 简述贪心法适用问题应具有的性质。

相关文章：