Test

---

1 （简单，2 分）

判断并给出下列表达式的渐进复杂度（使用大 O、Θ 或 o 说明紧确界），并简要说明理由：

(a) $f(n)=3n^2+100n\log n + 2000$。

(b) $g(n)=n\log n + 0.5n\log\log n$。

(c) $h(n)=\sqrt{n}\cdot \log n + n^{0.49}$。

---

2（循环复杂度，4 分）

分析以下代码的时间复杂度（以比较次数为单位），写出渐进上界与紧确界：

for (int i=1;i<=n;i++){
  for (int j=i;j<=n;j+=i){
     // O(1)
  }
}

---

3（调和级数与约计，4 分）

设 $T(n)=\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor$. 证明 $T(n)=\Theta(n\log n)$。

---

4（递推与主定理，5 分）

对于递推式 $T(n)=3T\left(\frac{n}{3}\right)+\frac{n}{\log n},\quad T(1)=\Theta(1),$ 确定 $T(n)$ 的渐进复杂度（证明思路要写明是用主定理、第 i 层代价估计或递归树）。

---

5（主定理边界情形，5 分）

令 $T(n)=2T\left(\frac{n}{2}\right)+\frac{n}{\log n}.$ 说明该式为什么不直接落入主定理的三类中的严格形式，并给出 $T(n)$ 的渐进复杂度及证明。

---

6（递归树与精确项，6 分）

设递推 $T(n)=T(n-1)+T(\lfloor n/2\rfloor)+1,\quad T(1)=1.$ 给出 $T(n)$ 的渐进上下界（尽可能紧），并说明关键推导步骤。

---

7（分治开销累加，5 分）

算法对长度为 n 的数组执行如下分治：把数组分成三等份，递归处理前两部分（长度约为 n/3），并对整段做一次线性级别的合并操作（Θ(n)）。写出该算法的时间复杂度并证明。

---

8（最坏/平均/期望复杂度对比，6 分）

快速排序（随机化基准）在最坏情况和平均情况的时间复杂度分别为多少？请说明平均情况的主要推导思路（可用递推或概率分析），并写出期望比较次数的 Θ 表达式。

---

9（摊还分析 — 动态数组，6 分）

一个动态数组按以下策略扩容：初始容量为 1，每当扩容需要时把容量扩大为原来的 1.5 倍（向上取整）。假设插入 n 次，推导总时间的摊还复杂度并说明是否仍为 $O(1)$ 摊还。提示：用费用法或聚合法证明。

---

10（摊还分析 — 表格链式删除，6 分）

有一个支持 push, pop, multipop(k) 操作的栈，multipop(k) 最多弹出 k 个元素。证明在任意序列的 m 次操作中，总的时间为 $O(m)$（即 multipop 的摊还代价是常数级），并给出证明思路。

---

11（图算法时间复杂度，6 分）

(a) 使用邻接表表示的图，经典的 DFS（深度优先搜索）在有向图上从所有未访问节点触发一次遍历的时间复杂度为何？写出对 $n$（顶点数）和 $m$（边数）的精确 Θ 表达式并说明。

(b) Dijkstra 算法在用斐波那契堆实现时的时间复杂度为何？给出对 $n,m$ 的表示并解释每项来源。

---

12（字符串匹配平均复杂度，6 分）

设文本长度为 $n$，模式长度为 $m$。朴素字符串匹配算法在最坏情况下复杂度是 $O(nm)$。请给出：

(a) 一个能达到 $\Theta(nm)$ 的最坏情况实例（文本与模式）；

(b) 若文本与模式均为等概率的字符序列（字母表大小常数），朴素算法的期望比较次数为多少（写出 Θ 表达式并说明大致推理）。

---

13（主定理变体 — 多项式因子，6 分）

求解递推： $T(n)=aT\left(\frac{n}{b}\right)+n(\log n)^k$ 其中 $a\ge 1,b>1,k$ 为常数。讨论当 $a=b^c$ 且 $c$ 与 $k$ 的相对大小不同（$c>1, c=1, c<1$）时 $T(n)$ 的渐进行为（给出三种情形结论并说明理由）。

---

14（递推中整数下界/上界细节，7 分）

考虑递推： $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+n,$ 给出 $T(n)=\Theta(n\log n)$ 的严谨证明，注意处理向下/向上取整带来的常数项。

---

15（概率算法复杂度 — Quickselect，7 分）

分析随机化选择（Quickselect）算法找第 k 小元素的期望时间复杂度（对任意固定 k）。给出递推并解出期望复杂度，说明关键概率步骤。

---

16（复杂性类直观题，5 分）

解释下列术语并给出一个典型问题示例：P、NP、NP-完全、对数空间 L、随机化复杂度类 BPP（简要要点即可，不需严格定义证明）。

---

17（FFT 时间复杂度推导，5 分）

快速傅里叶变换（FFT）对长度为 $n=2^k$ 的向量的时间复杂度为 $O(n\log n)$。用递归关系推导此复杂度并说明常数因子的来源（例如每层工作量与层数）。

---

18（比较复杂度与下界，8 分）

(a) 对于比较排序，证明任何基于比较的排序算法在最坏情况下需做 $\Omega(n\log n)$ 次比较（用決策树论证）。

(b) 假设输入只包含 $0/1$ 且已知有恰好 $k$ 个 1，设计比 $O(n\log n)$ 更快的排序（计数或基数思想）并给出其时间复杂度。

---

19（复杂度等价变换与渐进符号识别，4 分）

说明下列断言是否正确，并给出证明或反例：

(a) 若 $f(n)=O(g(n))$ 且 $g(n)=o(h(n))$，则 $f(n)=o(h(n))$。

(b) 若 $f(n)=\Theta(g(n))$ 且 $g(n)=\Theta(h(n))$，则 $f(n)=\Theta(h(n))$。

---

20（挑战题：递归带参数下界，10 分）

设递推 $T(n)=T(\alpha n)+T((1-\alpha)n)+cn$ 其中常数 $0<\alpha<1$ 且 $c>0$。证明 $T(n)=\Theta(n\log n)$（或指出哪些条件需要额外假定，例如 $\alpha$ 是否为常数且不依赖于 n），并给出证明要点（可用递归树或主定理类比，自行控制截断层数并估计每层代价）。

---