算法设计与分析 - 基本概念与解递归方程

发布时间： 2025-07-04 18:44:32 更新时间： 2025-07-04 18:44:32

🕒 阅读时间：3 分钟 📝 字数：803 👀 阅读量： Loading...

📚 参考书籍

计算机算法设计与分析(第5版)
ISBN编号：9787121344398

💡 有趣的发现： ISBN编号相同却有两个不同封面的书，可能是出版商重印了。

---

🔍 一些基本概念

计算复杂度

• 上界(Upper Bound): 算法复杂度的上界用大O表示法表示，即 O(f(n))O(f(n))，表示算法的运行时间不会超过 f(n)f(n) 的常数倍。

• 确界(Tight Bound): 算法复杂度的确界用Θ表示法表示，即 Θ(f(n))Θ(f(n))，表示算法的运行时间既有上界又有下界，都是 f(n)f(n) 的常数倍。

• 下界(Lower Bound): 算法复杂度的下界用Ω表示法表示，即 Ω(f(n))Ω(f(n))，表示算法的运行时间至少是 f(n)f(n) 的常数倍。

注意：一般而言，我们通常考虑最差情况的复杂度，也就是 O(f(n))O(f(n))。

验证复杂度公式

极限法验证

原理：通过计算 T(n)T(n) 与 f(n)f(n) 的比值极限来确定渐进复杂度。

• 若 lim⁡n→∞T(n)f(n)=0\lim_{n\to\infty}\frac{T(n)}{f(n)}=0，则 T(n)=o(f(n))T(n)=o(f(n))
• 若 lim⁡n→∞T(n)f(n)=∞\lim_{n\to\infty}\frac{T(n)}{f(n)}=\infty，则 T(n)=ω(f(n))T(n)=\omega(f(n))
• 若 lim⁡n→∞T(n)f(n)=c\lim_{n\to\infty}\frac{T(n)}{f(n)}=c（c>0c>0 为常数），则 T(n)=Θ(f(n))T(n)=\Theta(f(n))

验证方法：对于给定的 T(n)T(n) 和 f(n)f(n)，计算 lim⁡n→∞T(n)f(n)\lim_{n\to\infty}\frac{T(n)}{f(n)}。

例子：对于 T(n)=2n2+3n+1T(n)=2n^2+3n+1 和 f(n)=n2f(n)=n^2，计算极限 lim⁡n→∞2n2+3n+1n2=lim⁡n→∞(2+3n+1n2)=2\lim_{n\to\infty}\frac{2n^2+3n+1}{n^2}=\lim_{n\to\infty}(2 + \frac{3}{n} +\frac{1}{n^2})=2

这是一个正常数，所以 T(n)=Θ(n2)T(n)=\Theta(n^2)。

提示：一般而言，我们只需要考虑最高次项的系数，除非实在是不确定才会用到这个公式。

💻 解递归方程

主定理方法

主定理（Master Theorem）是分析递归算法时间复杂度的一个强大工具，适用于形如 T(n)=aT(nb)+f(n)T(n) = aT(\frac{n}{b}) + f(n) 的递归方程，其中：

• a≥1a \geq 1 是子问题的数量
• b>1b > 1 是子问题规模缩减因子
• f(n)f(n) 是分解和合并的额外工作量

主定理的三种情况：

1. 若 f(n)=O(nlog⁡ba−ϵ)f(n) = O(n^{\log_b a-\epsilon}) 对某个 ϵ>0\epsilon > 0：
   • 此时 T(n)=Θ(nlog⁡ba)T(n) = \Theta(n^{\log_b a})
2. 若 f(n)=Θ(nlog⁡balog⁡kn)f(n) = \Theta(n^{\log_b a}\log^k n) 对某个 k≥0k \geq 0：
   • 此时 T(n)=Θ(nlog⁡balog⁡k+1n)T(n) = \Theta(n^{\log_b a}\log^{k+1} n)
3. 若 f(n)=Ω(nlog⁡ba+ϵ)f(n) = \Omega(n^{\log_b a+\epsilon}) 对某个 ϵ>0\epsilon > 0，且对某个常数 c<1c < 1 和足够大的 nn 有 af(nb)≤cf(n)af(\frac{n}{b}) \leq cf(n)：
   • 此时 T(n)=Θ(f(n))T(n) = \Theta(f(n))

例子：分析归并排序 T(n)=2T(n2)+nT(n) = 2T(\frac{n}{2}) + n

• 这里 a=2a = 2, b=2b = 2, f(n)=nf(n) = n
• 计算 nlog⁡ba=nlog⁡22=n1=nn^{\log_b a} = n^{\log_2 2} = n^1 = n
• 因为 f(n)=Θ(nlog⁡ba)f(n) = \Theta(n^{\log_b a})，符合情况2（k=0k=0）
• 所以 T(n)=Θ(nlog⁡n)T(n) = \Theta(n\log n)

递归树方法

递归树方法是一种可视化的方式来分析递归方程。

基本步骤：

1. 将递归方程表示为一棵树，根节点代表原问题
2. 每个内部节点表示一个子问题，边表示递归调用
3. 对每一层计算总的工作量
4. 累加所有层的工作量得到总复杂度

例子：分析 T(n)=2T(n/2)+nT(n) = 2T(n/2) + n

递归树：

• 第0层（根）：工作量 = nn
• 第1层：2个子问题，每个工作量 = n/2n/2，总工作量 = 2⋅(n/2)=n2 \cdot (n/2) = n
• 第2层：4个子问题，每个工作量 = n/4n/4，总工作量 = 4⋅(n/4)=n4 \cdot (n/4) = n
• …
• 第log⁡2n\log_2 n层：nn个子问题，每个工作量 = 11，总工作量 = nn

总工作量 = n+n+...+nn + n + ... + n (log⁡2n+1\log_2 n + 1项) = Θ(nlog⁡n)\Theta(n\log n)

代入法

代入法（也称为归纳法）是通过猜测解的形式，然后使用数学归纳法证明猜测是正确的。

基本步骤：

1. 猜测解的形式（通常基于直觉或经验）
2. 使用归纳法证明这个猜测

例子：证明 T(n)=2T(n/2)+nT(n) = 2T(n/2) + n 的解为 T(n)=O(nlog⁡n)T(n) = O(n\log n)

假设 T(n)≤cnlog⁡nT(n) \leq cn\log n 对某个常数 c>0c > 0

验证： T(n)=2T(n/2)+n≤2c(n/2)log⁡(n/2)+n=cnlog⁡(n/2)+n=cnlog⁡n−cnlog⁡2+n=cnlog⁡n−cn+nT(n) = 2T(n/2) + n \leq 2c(n/2)\log(n/2) + n = cn\log(n/2) + n = cn\log n - cn\log 2 + n = cn\log n - cn + n

当 c≥1c \geq 1 时，T(n)≤cnlog⁡nT(n) \leq cn\log n，假设成立。

这要没ai,写latex得累死…