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

📚 参考书籍

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

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

🔍 一些基本概念

计算复杂度

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

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

• 下界(Lower Bound): 算法复杂度的下界用Ω表示法表示，即 $\mathrm{\Omega }(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)=\mathrm{\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)=\mathrm{\Theta }(n^2)$。

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

💻 解递归方程

主定理方法

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

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

主定理的三种情况：

1. 若 $f(n)=O(n^{{\log }_{b}a-ϵ})$ 对某个 $ϵ>0$：
   • 此时 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$
2. 若 $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n)$ 对某个 $k\ge 0$：
   • 此时 $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k+1}n)$
3. 若 $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ 对某个 $ϵ>0$，且对某个常数 $c<1$ 和足够大的 $n$ 有 $af(\frac{n}{b})\le cf(n)$：
   • 此时 $T(n)=\mathrm{\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)=\mathrm{\Theta }(n^{{\log }_{b}a})$，符合情况2（$k=0$）
• 所以 $T(n)=\mathrm{\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$项) = $\mathrm{\Theta }(n\log n)$

代入法

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

基本步骤：

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

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

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

验证： $T(n)=2T(n/2)+n\le 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\ge 1$ 时，$T(n)\le cn\log n$，假设成立。

这要没ai,写latex得累死…