本文最后更新于：2025年11月29日下午

【一周一算法】第六周：分治算法通论 · 思考题与练习详解

“分治思想决定了算法结构，而主定理决定了时间复杂度的命运。”

在《第六周 · 分治算法通论》中，我们学习了如何将所有结构良好的递归复杂度统一写成：

T(n)=aT(n/b)+f(n)

并用 主定理（Master Theorem） 在 几秒钟 内判断时间复杂度。

本篇我们用同样深入浅出的方式，逐题讲解上周的思考题。

🧩 思考题一：

T(n)=4T(n/2)+n 的复杂度是多少？

❓ 思路分析

主定理格式：

a = 4
b = 2
f(n) = n

先计算关键指数：

k=\log_b a=\log_2 4=2

对比 f(n)=n=n¹ 可以看出：

f(n) = n¹
n^{log_b a} = n²

明显：

f(n)=O(n^{k-\epsilon}) \quad(\epsilon=1)

即 f(n) 比 n² 小一个数量级

命中 主定理 Case 1（递归主导）

✅ 答案

1	`T(n) = Θ(n^2)`

💡 解释

该递归树在顶部只有一次 n 消耗，而底层因为 “4 个子问题 × log(n) 层” 迅速爆炸，主导整体复杂度。

🧩 思考题二：

T(n)=9T(n/3)+n² log n 的复杂度是多少？

❓ 思路分析

主定理参数：

a = 9
b = 3
f(n) = n² log n

关键指数：

k=\log_3 9=2

那么：

n^{k} = n²
f(n) = n² log n = n^k log¹ n

这与 Case 2 完美匹配：

f(n) = Θ(n^k log^m n)，复杂度为 Θ(n^k log^{m+1} n)

这里 m = 1

✅ 答案

1	`T(n) = Θ(n^2 log^2 n)`

💡 解释

递归部分与合并部分同阶，但 f(n) 多了一个 log n，使其略强一层，最终整体多出一个 log。

🧩 思考题三：

T(n)=2T(n/4)+√n 的复杂度是多少？

这是许多同学最容易判断错的一题。

❓ 思路分析

主定理参数：

a = 2
b = 4
f(n) = n^{1/2}

求关键指数：

k=\log_4 2=\frac{1}{2}

发现了没？

n^k = n^{1/2}
f(n) = n^{1/2}

它们 完全一样！

所以它符合：

Case 2：f(n)=Θ(n^k) （即 log^0 n）

于是结果为：

1	`T(n) = Θ(n^{1/2} log n)`

🧮 验证

递归树每层成本大致相同（n^{1/2}），共有 log₄ n = (1/2) log₂ n 层 → 成本累加 = n^{1/2} × log n

✅ 答案

1	`T(n) = Θ(√n log n)`

🧩 思考题四（附加）：

为什么主定理只比较 f(n) 与 n^{log_b a}？

为了帮助你真正理解主定理，我们补充一个关键问题：

✔ 因为这两者分别代表：

n^{log_b a}：递归树的“宽度”指数 → a 个子问题 × b 的分割方式组成的增长速度
f(n)：每层合并的“高度”成本

递归树本质上是：

顶层：         f(n)
第二层：      a·f(n/b)
第三层：     a²·f(n/b²)
...
底层：        n → 1 时的叶子成本

其中关键项：

a·(1/b^k) 给出递归增长速度
f(n) 给出合并成本规模

谁增长更快，谁主导复杂度。这就是主定理所有 case 的数学来源。

🔍 思考题五（挑战）：

给你一个递归式，判断它是否能用主定理求解：

T(n)=T(n/2)+T(n/3)+n
T(n)=2T(n/2)+n/log n
T(n)=n·T(n/2)+n²
T(n)=3T(n/4+7)+log n

✔ 答案

❌ 不能（子问题规模不一致 → 需 Akra-Bazzi）
❌ 不完全能（f(n)=n/log n 不是简单多项式）
❌ 不符合 a,T(n/b) 结构（a=n，不是常数）
❌ 子问题规模 n/4+7 非标准形式

主定理适用范围很窄，这是它的限制。

🧪 C++ 小实验：验证 T(n)=2T(n/4)+√n 是不是 n^{1/2} log n？

可以写个递归计数器做对比：

#include <iostream>
#include <cmath>

long long solve(int n) {
    if (n <= 1) return 1;
    long long left = solve(n / 4);
    long long right = solve(n / 4);
    return left + right + std::sqrt(n);
}

int main() {
    for (int n : {256, 1024, 4096, 16384, 65536}) {
        std::cout << "n=" << n 
                  << " cost=" << solve(n)
                  << "  approx=" << std::sqrt(n) * log2(n)
                  << std::endl;
    }
    return 0;
}

你会看到：

实际 cost 和 √n·log n 曲线非常接近
完全符合主定理 Case 2 的预期

📘 总结

本周练习主要考察：

知识点	要求
主定理 Case 1	f(n) 比 n^{log_b a} 小
主定理 Case 2	f(n) 与 n^{log_b a} 同阶
主定理 Case 3	f(n) 更强，需要正则条件
不能使用主定理的情况	子问题规模不一致、f(n) 非多项式、a 非常数等