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

📚 参考书籍

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

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

---

🔍 一些基本概念

计算复杂度

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

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

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

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

验证复杂度公式

极限法验证

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

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

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

例子：对于 $T(n)=2n^2+3n+1$ 和 $f(n)=n^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)=\Theta(n^2)$。

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

💻 解递归方程

主定理方法

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

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

主定理的三种情况：

1. 若 $f(n) = O(n^{\log_b a-\epsilon})$ 对某个 $\epsilon > 0$：
   • 此时 $T(n) = \Theta(n^{\log_b a})$
2. 若 $f(n) = \Theta(n^{\log_b a}\log^k n)$ 对某个 $k \geq 0$：
   • 此时 $T(n) = \Theta(n^{\log_b a}\log^{k+1} n)$
3. 若 $f(n) = \Omega(n^{\log_b a+\epsilon})$ 对某个 $\epsilon > 0$，且对某个常数 $c < 1$ 和足够大的 $n$ 有 $af(\frac{n}{b}) \leq cf(n)$：
   • 此时 $T(n) = \Theta(f(n))$

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

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

递归树方法

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

基本步骤：

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

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

递归树：

• 第0层（根）：工作量 = $n$
• 第1层：2个子问题，每个工作量 = $n/2$，总工作量 = $2 \cdot (n/2) = n$
• 第2层：4个子问题，每个工作量 = $n/4$，总工作量 = $4 \cdot (n/4) = n$
• ...
• 第$\log_2 n$层：$n$个子问题，每个工作量 = $1$，总工作量 = $n$

总工作量 = $n + n + ... + n$ ($\log_2 n + 1$项) = $\Theta(n\log n)$

代入法

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

基本步骤：

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

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

假设 $T(n) \leq cn\log n$ 对某个常数 $c > 0$

验证： $T(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 \geq 1$ 时，$T(n) \leq cn\log n$，假设成立。

这要没ai,写latex得累死...