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

📚 参考书籍

计算机算法设计与分析(第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得累死…