📚 覆盖：第 1–8 讲 · 建议：先独立完成再看解答；证明题要写完整论证，不能只给结论。

第一部分：正确性与渐近分析（第 1–2 讲）

题 1（5 分）

对下面的函数：

func Search(a []int, x int) int {
    for i := 0; i < len(a); i++ {
        if a[i] == x { return i }
    }
    return -1
}

(a) 写出一个循环不变式。 (b) 完成初始化、保持、终止三步证明。 (c) 为什么"终止"这一步不能省略？

题 2（6 分）

用定义（给出具体的 c、n₀）证明或反驳：

(a) n² + 3n = Θ(n²) (b) 2^(n+1) = O(2ⁿ) (c) 2^(2n) = O(2ⁿ) (d) n log n = O(n^1.01) (e) log(n!) = Θ(n log n)

题 3（4 分）

按增长率从慢到快排序，相同量级的标出：

n^(1/log₂ n)、4^(log₂ n)、log(n!)、n log n、2^(log₂ n)、n!、(log n)^(log n)、n²

题 4（4 分）

求下列代码段的复杂度并说明理由：

// (a)
for i := 1; i <= n; i++ {
    for j := i; j <= n; j += i { count++ }
}

// (b)
for i := n; i > 0; i /= 2 {
    for j := 0; j < i; j++ { count++ }
}

// (c)
for i := 1; i*i <= n; i++ { count++ }

// (d)
for i := 1; i <= n; i++ {
    j := i
    for j > 0 { j /= 2 }
}

题 5（3 分）

你把 n 从 10⁴ 提到 10⁵，运行时间从 0.2 s 变成 20 s。

(a) 最可能的复杂度是什么？ (b) 若 n 再提到 10⁶，预计多久？ (c) 若目标是 10⁶ 时不超过 10 s，需要把算法改进到什么量级？

第二部分：递归式（第 3 讲）

题 6（6 分）

用主定理求解，指出情形编号：

(a) T(n) = 4T(n/2) + n (b) T(n) = 4T(n/2) + n² (c) T(n) = 4T(n/2) + n³ (d) T(n) = 2T(n/4) + √n (e) T(n) = 3T(n/3) + n/2 (f) T(n) = 16T(n/4) + n²

题 7（4 分）

T(n) = 2T(n/2) + n/log n

(a) 为什么主定理三种情形都不适用？ (b) 用递归树求出它的解。

题 8（4 分）

指出下面"证明"的错误，并给出正确的论证：

设 T(n) = 2T(n/2) + n。归纳假设 T(n/2) = O(n/2)，则 T(n) = 2·O(n/2) + n = O(n) + n = O(n)。

题 9（3 分）

用换元法求解 T(n) = 2T(√n) + log n。

第三部分：摊还分析（第 4 讲）

题 10（6 分）

一个动态数组，容量满时扩容为原来的 3 倍。

(a) n 次 append 的总代价是多少？摊还代价呢？ (b) 若改成每次扩容 +100 个位置，总代价是多少？ (c) 从(a)(b)总结出扩容策略的一般规律。

题 11（6 分）

k 位二进制计数器同时支持 INCREMENT 和 DECREMENT。

(a) 证明摊还代价不再是 O(1)。 (b) 构造一个使摊还退化为 Θ(k) 的操作序列。 (c) 若只支持 INCREMENT，用势能法证明摊还 O(1)。

题 12（5 分）

一个数据结构支持 Push（O(1)）和 Flush（把当前所有元素清空并处理，代价 = 元素个数）。

(a) 用聚合法证明每个操作摊还 O(1)。 (b) 用记账法给出摊还代价的分配。 (c) 给出一个势能函数并验证。

题 13（4 分）

动态数组的收缩策略：

(a) 若"size < capacity/2 就收缩到一半"，构造一个使摊还退化为 Θ(n) 的操作序列。 (b) 为什么改成 “size < capacity/4 才收缩” 就能恢复 O(1)？ (c) 这个"滞后区"思想还能用在什么工程场景？

第四部分：线性结构（第 5–6 讲）

题 14（5 分）

(a) 列出数组、动态数组、单链表、双链表在六个操作上的复杂度。 (b) 双链表唯一无可替代的能力是什么？ (c) 设计一个 O(1) 的 LRU 缓存，说明为什么必须"散列表 + 双链表"。

题 15（4 分）

Go 中下面的代码有什么问题？

type Queue struct{ data []*Item }
func (q *Queue) Push(x *Item) { q.data = append(q.data, x) }
func (q *Queue) Pop() *Item {
    x := q.data[0]
    q.data = q.data[1:]
    return x
}

(a) 指出两个独立的问题。 (b) 给出正确的实现。

题 16（5 分）

用两个栈实现一个队列。

(a) 给出实现。 (b) 证明每个操作的摊还代价是 O(1)。 (c) 单次 Dequeue 的最坏代价是多少？

题 17（5 分）

数组 a，对每个 i 求"右边第一个比 a[i] 大的元素下标"。

(a) 写出单调栈解法。 (b) 证明它是 Θ(n) 而不是 Θ(n²)。 (c) 如果改求"左边第一个更小的"，代码怎么改？

第五部分：散列表（第 7–8 讲）

题 18（6 分）

链地址法，n 个键、m 个槽。

(a) 推导 SUHA 下不成功查找的期望代价。 (b) 推导成功查找的期望代价。 (c) 为什么维持 α = O(1) 就能得到 O(1) 操作？这需要什么机制，代价是多少？

题 19（6 分）

开放寻址，装填因子 α。

(a) 推导不成功查找的期望探查次数 1/(1−α)。 (b) 填一张 α = 0.5 / 0.75 / 0.9 / 0.95 / 0.99 时的探查次数表。 (c) 为什么链地址法可以容忍更高的 α？

题 20（8 分）

(a) 全域散列的定义中，概率是对什么取的？为什么这一点关键？ (b) 证明：若 H 是全域族，任意键 k 所在链的期望长度 < α + 1。 (c) 什么是散列洪水攻击？为什么"换更复杂的散列函数"防不住它？ (d) Java 的 HashMap 把长链转成红黑树，这个防御的思路与随机化种子有何不同？

题 21（6 分）

布隆过滤器，n 个元素、m 位、k 个散列函数。

(a) 推导误判率公式与最优 k。 (b) 目标误判率 1%，每元素需要多少位？ (c) 内存只够 5 位/元素时，最优 k 和误判率各是多少？ (d) 为什么不能删除？计数布隆过滤器的代价是什么？

参考解答

题 1

(a) 不变式：每次迭代开始前，a[0..i-1] 中不含 x。

(b)

  • 初始化：i = 0 时 a[0..-1] 是空切片，平凡成立。✓
  • 保持：若迭代开始前 a[0..i-1] 不含 x，本次检查 a[i]：若相等则返回 i（正确）；否则 a[0..i] 仍不含 x，i 加 1 后不变式成立。✓
  • 终止：循环在 i = len(a) 时结束，不变式给出 a[0..len(a)-1] 不含 x，返回 −1 正确。✓

(c) 因为终止步是把"循环中途的部分性质"兑换成"我们真正要的结论"的唯一环节。一个不变式如果在终止时推不出目标结论，它再真也没有用。

题 2

(a) 成立。取 c₁ = 1、c₂ = 4、n₀ = 1：对 n ≥ 1，n² ≤ n²+3n ≤ 4n²。

(b) 成立。2^(n+1) = 2·2ⁿ，取 c = 2、n₀ = 1。

(c) 不成立。2^(2n)/2ⁿ = 2ⁿ → ∞，不存在常数 c 使 2^(2n) ≤ c·2ⁿ。⭐ 这是"指数的底/系数不能随意吸收"的关键对照。

(d) 成立。n log n / n^1.01 = log n / n^0.01 → 0（任何多项式打败任何多对数）。

(e) 成立。由 Stirling：log(n!) = n log n − n log e + O(log n) = Θ(n log n)。

题 3

n^(1/log₂ n) = 2  (常数)
< 2^(log₂ n) = n   ——等于 n
< n log n = log(n!)  ——这两个同量级 Θ(n log n)
< n² = 4^(log₂ n)    ——这两个同量级 Θ(n²)
< (log n)^(log n)     ——= 2^(log log n · log n)，超多项式但次指数
< n!

排序：n^(1/log n) ≺ 2^(log₂n) ≺ n log n = log(n!) ≺ n² = 4^(log₂n) ≺ (log n)^(log n) ≺ n!

题 4

(a) Θ(n log n)。内层执行 n/i 次，总和 Σ n/i = n·Hₙ = Θ(n log n)。⚠️ 不是 Θ(n²)。

(b) Θ(n)。总和 n + n/2 + n/4 + … < 2n（几何级数）。

(c) Θ(√n)。

(d) Θ(n log n)。外层 n 次，内层每次 log i ≤ log n 次；下界由后一半的 i ≥ n/2 给出 Θ(n log n)。

题 5

(a) n 增大 10 倍，时间增大 100 倍 ⟹ Θ(n²)。

(b) 再增 10 倍 ⟹ 时间 ×100 ⟹ 约 2000 s ≈ 33 分钟。

(c) 需要在 10⁶ 时 ≤ 10 s。若是 Θ(n log n)：从 10⁴ 的基准外推，10⁶ 时约 0.2 × (10⁶·20)/(10⁴·13) ≈ 30 s——仍略超。目标应是 Θ(n log n) 并优化常数，或 Θ(n)。

题 6

log_b a f(n) 情形 解
(a) log₂4 = 2 n = O(n^(2−ε)) 1 Θ(n²)
(b) 2 n² = Θ(n²) 2 (k=0) Θ(n² log n)
(c) 2 n³ = Ω(n^(2+ε))，正则 ✓ 3 Θ(n³)
(d) log₄2 = 0.5 √n = Θ(n^0.5) 2 (k=0) Θ(√n log n)
(e) log₃3 = 1 n/2 = Θ(n) 2 (k=0) Θ(n log n)
(f) log₄16 = 2 n² = Θ(n²) 2 (k=0) Θ(n² log n)

题 7

(a) log₂2 = 1，f(n) = n/log n。与 n¹ 比：f(n)/n = 1/log n → 0，所以 f 比 n 小；但小的程度不是多项式级（不存在 ε 使 n/log n = O(n^(1−ε))），情形 1 不适用；显然也不是 Θ(n log^k n)（k ≥ 0），情形 2 不适用；f 更小，情形 3 不适用。

(b) 递归树第 i 层有 2ⁱ 个节点，每个代价 (n/2ⁱ)/log(n/2ⁱ)，该层总和 n/(log n − i)。求和：

T(n) = Σ_{i=0}^{log n − 1} n/(log n − i) = n · Σ_{j=1}^{log n} 1/j = n·H_{log n} = Θ(n log log n)

题 8

错误在最后一步。归纳法必须精确证出归纳假设的同一形式：要证 T(n) ≤ cn（同一个 c），但推导只得到 T(n) ≤ cn + n = (c+1)n——常数变了。这种"渐近地做归纳"能证明任何结论，是无效的。

正确论证：T(n) = 2T(n/2)+n 的解是 Θ(n log n)，不是 O(n)。用代换法猜 T(n) ≤ cn log n：T(n) ≤ 2·c(n/2)log(n/2) + n = cn log n − cn + n ≤ cn log n（取 c ≥ 1）。✓

题 9

令 m = log₂ n（n = 2^m），S(m) = T(2^m)：

S(m) = 2S(m/2) + m    ⟹ 主定理情形 2 ⟹ S(m) = Θ(m log m)
⟹ T(n) = Θ(log n · log log n)

题 10

(a) 扩容发生在容量 1, 3, 9, …, 3^k 处，拷贝总量 1+3+9+…+3^k < 3^(k+1)/2 = O(n)。加上 n 次写入，总代价 Θ(n)，摊还 Θ(1)。

(b) 扩容在 100, 200, …, n 处，拷贝总量 100+200+…+n = Θ(n²/100) = Θ(n²)，摊还 Θ(n)。

(c) ⭐ 必须几何增长（增长因子 > 1 的任意常数都行），线性增量会导致摊还退化为线性。因子取 2 还是 1.5 或 3 只影响常数与内存复用效率。

题 11

(a)(b) 取计数器处于 0111…1（k−1 个 1）与 1000…0 的边界，交替执行 INCREMENT 和 DECREMENT：

0111…1 --INC--> 1000…0   翻转 k 位
1000…0 --DEC--> 0111…1   翻转 k 位

每次操作都是 Θ(k)，摊还退化为 Θ(k)。势能法失效的原因：INCREMENT 减少的势能被 DECREMENT 立刻加回来。

(c) 取 Φ = 计数器中 1 的个数 b。第 i 次 INCREMENT 把 tᵢ 个 1 变 0、1 个 0 变 1：

cᵢ = tᵢ + 1，ΔΦ = 1 − tᵢ  ⟹  ĉᵢ = 2 = Θ(1)

题 12

(a) 聚合法：n 个操作中，每个元素最多被 Flush 处理一次，而它必须先被 Push 进来。故总代价 ≤ 2n，摊还 O(1)。

(b) 记账法：Push 收 2 元（1 元付压入，1 元存在该元素上）；Flush 收 0 元（每个元素用自己的存款付处理费）。总信用永不为负。✓

(c) 势能法：取 Φ = 当前元素个数。

  • Push：c = 1，ΔΦ = +1，ĉ = 2
  • Flush（清 k 个）：c = k，ΔΦ = −k，ĉ = 0 ✓

题 13

(a) 数组刚好半满时：push（触发扩容拷贝 n）→ pop（size 降到 capacity/2 以下，触发收缩拷贝 n）→ push → pop → …每次操作 Θ(n)。

(b) 收缩阈值 capacity/4 时，一次扩容或收缩之后，size 距离下一个触发点至少还有 capacity/4，需要至少 capacity/4 次操作。几何级数论证重新成立，摊还回到 O(1)。

(c) 任何"自动伸缩"机制都需要滞后区：线程池扩缩容、连接池、Kubernetes HPA、缓存淘汰阈值、UI 的自动滚动触发。否则会在阈值处抖动。

题 14

(a)

操作 静态数组 动态数组 单链表 双链表
Get(i) Θ(1) Θ(1) Θ(n) Θ(n)
InsertFirst Θ(n) Θ(n) Θ(1) Θ(1)
DeleteFirst Θ(n) Θ(n) Θ(1) Θ(1)
InsertLast — Θ(1)摊还 Θ(1) Θ(1)
DeleteLast Θ(1) Θ(1) Θ(n) Θ(1)
持有指针时删除 Θ(n) Θ(n) Θ(n) Θ(1)

(b) 已持有节点指针时的 O(1) 删除，且删除不会使其他节点的指针失效。

(c) LRU 需要两件事：① 按 key 在 O(1) 内定位节点（散列表）；② 把该节点从访问顺序链表中 O(1) 摘除并移到表头（双链表）。散列表存 key → *Node，链表维护访问顺序。单用散列表无法维护顺序；单用链表无法 O(1) 定位。

题 15

(a)

  1. 内存泄漏：q.data = q.data[1:] 只是移动切片头，底层数组前段永远不被回收；且出队元素是指针，被底层数组持续持有，GC 无法回收它指向的对象。长期运行内存单调增长。
  2. 底层数组不断重新分配：切片头不断右移、容量递减，append 会反复触发新分配和整体拷贝。

(b) 用环形缓冲，且出队时把槽位清零：

func (q *Queue) Pop() *Item {
    x := q.data[q.head]
    q.data[q.head] = nil // 断开引用
    q.head = (q.head + 1) % len(q.data)
    q.size--
    return x
}

题 16

(a)

type MyQueue struct{ in, out []int }

func (q *MyQueue) Enqueue(x int) { q.in = append(q.in, x) }

func (q *MyQueue) Dequeue() (int, bool) {
    if len(q.out) == 0 {
        for len(q.in) > 0 { // 整体倒过来，顺序自然翻转
            n := len(q.in) - 1
            q.out = append(q.out, q.in[n])
            q.in = q.in[:n]
        }
    }
    if len(q.out) == 0 { return 0, false }
    n := len(q.out) - 1
    x := q.out[n]
    q.out = q.out[:n]
    return x, true
}

(b) 记账法：Enqueue 收 3 元（1 元压入 in，1 元将来从 in 弹出，1 元将来压入 out）；Dequeue 收 1 元。每个元素最多被搬运一次，摊还 O(1)。

(c) 最坏 Θ(n)——恰好在 out 为空且 in 有 n 个元素时。

题 17

(a) 见第 6 讲的 NextGreater。

(b) 每个下标恰好入栈一次、出栈一次。内层 while 的总执行次数 = 总出栈次数 ≤ n。故总代价 Θ(n)。（记账法：入栈时预付出栈费用。）

(c) 从右往左遍历，或把比较符号从 < 改为 >——即维护一个单调递增栈。关键是想清楚"栈中保留的是什么样的候选"。

题 18

(a) 链 T[h(k)] 的期望长度 = Σ_{i=1}^{n} Pr[键 i 落在该槽] = n/m = α。加上计算散列与寻址的 Θ(1)，期望代价 Θ(1+α)。

(b) 设查找第 i 个插入的键，头插法下需检查 1 + (在它之后插入且同槽的键数)：

E = (1/n)Σ_{i=1}^{n}(1 + Σ_{j=i+1}^{n} 1/m) = 1 + (n−1)/(2m) = Θ(1+α)

(c) α = n/m = O(1) 意味着 m = Θ(n)，代价 Θ(1+α) = Θ(1)。需要再散列（rehash） 机制：α 超阈值时把 m 翻倍并重新插入所有元素，单次 Θ(n)，但由几何增长论证摊还 O(1)。

题 19

(a) 每次探查命中空槽的概率约为 1−α（因为约 α 比例的槽被占）。探查次数服从几何分布，期望 1/(1−α)。

(b)

α 0.5 0.75 0.9 0.95 0.99
1/(1−α) 2 4 10 20 100

(c) 链地址法的代价是 Θ(1+α)——线性，α = 5 也只是平均查 5 个元素；开放寻址是 1/(1−α)——在 α→1 时爆炸，且 α 不能超过 1。

题 20

(a) 概率是对 h 从函数族 H 中的随机选择取的，不是对键的分布取的。这一点关键：因为随机性来自算法自己，结论对任意输入都成立，攻击者无法构造最坏输入。

(b) 对键 k，定义指示变量 X_{kl} = 1[h(k)=h(l)]，由全域性 E[X_{kl}] ≤ 1/m。k 所在槽的其他元素数：

E[Nₖ] = Σ_{l≠k} E[X_{kl}] ≤ (n−1)/m < α

加上 k 自己，期望链长 < α + 1。∎

(c) 攻击者离线构造出大量散列值相同的键（如 HTTP POST 参数名），一次请求触发 n 次同槽插入，Θ(n²)，CPU 打满。换更复杂的散列函数没用，只要它是固定且公开的，攻击者就能离线算出碰撞集。必须引入攻击者不知道的随机性（进程启动时的随机种子）。

(d) 随机化种子是预防——让攻击者无法构造碰撞集；红黑树是兜底——承认碰撞可能发生，但把最坏代价从 O(n) 降到 O(log n)，使攻击收益不足。两者可以并用。

题 21

(a) 插入 n 个元素后某位仍为 0 的概率 ≈ e^{−kn/m}，误判率 FP ≈ (1−e^{−kn/m})^k。对 k 求导取极值得 k* = (m/n)ln2，代入得 FP = 0.6185^{m/n}。

(b) m/n = −log₂(0.01)/ln2 ≈ 6.64/0.693 ≈ **9.6 位**（约 1.2 字节），最优 k = 7。

(c) m/n = 5 ⟹ k* = 5×0.693 ≈ 3.5 → 取 3 或 4；FP = 0.6185^5 ≈ **9%**。

(d) 一个位可能被多个元素共享，清零会导致其他元素被误判为"不存在"（产生假阴性，破坏了布隆过滤器的核心保证）。计数布隆过滤器把每位换成 4 位计数器，空间变成 4 倍。