算法分析与设计

为什么要分析算法？

• 按难度对问题和算法进行分类
• 预测性能，比较算法，调整参数
• 更好地理解和改进实现和算法

算法分析

问题：

• 正确性 (Correctness)
• 时间效率 (time efficiency)
• 空间效率 (space efficiency)
• 最优性 (optimality)

方法：

• 实证分析 (Empirical analysis)
• 理论分析 (Theoretical analysis)

运行时间

程序的运行时间通常取决于输入规模，并随输入规模的增加而增加。

时间效率的实证分析

1. 编写实现算法的程序
2. 使用各种输入规模运行程序（例如，500、1000、2000等）
3. 测量实际运行时间（例如，在C/C++中使用clock()函数）
4. 绘制结果图表

时间效率的理论(Theoretical)分析

影响运行时间的两个主要因素：

1. 执行每个操作的成本(Cost) 取决于机器、编译器
2. 每个操作的执行频率(Frequency) 取决于算法、输入数据

时间效率是通过计算其基本操作执行的次数来衡量的， o作为输入规模的函数。 "用一个关于输入规模$n$的函数$f(n)$来表示算法的时间效率，其中$f(n)$表示算法执行基本操作的次数。"

• 基本操作：对算法运行时间贡献最大的操作（例如，算法最内层循环中最耗时的操作）
• 近似计算$c_{op}$和$C(n)$（忽略低阶项）

最佳情况、平均情况和最坏情况

对于某些算法，效率取决于输入的形式：

• 最坏情况：$C_{worst}(n)$ - 在大小为$n$的输入上执行基本操作的最大次数
• 最佳情况：$C_{best}(n)$ - 在大小为$n$的输入上执行基本操作的最小次数
• 平均情况：$C_{avg}(n)$ - 在大小为$n$的典型输入上执行基本操作的"平均"次数

增长的阶

假设$C(n) = \frac{1}{2}n(n-1)$，如果计算机的速度提高一倍，算法将运行多快？如果问题规模增加一倍，需要多长时间来求解？

关键因素：

• 不是给定$n$时执行的基本操作的确切数量
• 而是随着$n$的增加，基本操作的数量如何增长

忽略常数因子、常数和小输入规模，关注$n \to \infty$时的增长阶数。

渐近增长阶数

• 比较函数的方法，忽略常数因子和小输入规模
• 根据增长率对函数进行分类
  • $O(g(n))$：大O符号 - 增长速度不超过$g(n)$的函数$f(n)$类（最坏情况的上界）
  • $\Theta(g(n))$：大$\Theta$符号 - 增长速度与$g(n)$相同的函数$f(n)$类（最佳情况）
  • $\Omega(g(n))$：大$\Omega$符号 - 增长速度至少与$g(n)$一样快的函数$f(n)$类（最坏情况的下界）

大O符号($O$-notation)

上界。如果存在常数$c > 0$和$n_0 \geq 0$，使得对于所有$n \geq n_0$，有$t(n) \leq c \cdot g(n)$，则$t(n)$是$O(g(n))$。

例如，$t(n) = 100n + 5$，证明$t(n) \in O(n^2)$：

证明：对于所有$n \geq 1$，有$100n + 5 \leq 100n^2 + 5n^2 = 105n^2$（即取$c = 105$和$n_0 = 1$）。因此，$t(n) \in O(n^2)$。

大$\Omega$符号($\Omega$-notation)

下界。如果存在常数$c > 0$和$n_0 \geq 0$，使得对于所有$n \geq n_0$，有$t(n) \geq c \cdot g(n)$，则$t(n)$是$\Omega(g(n))$。

例如，$t(n) = n^3$，证明$t(n) \in \Omega(n^2)$：

证明：对于所有$n \geq 0$，有$n^3 \geq n^2$（即取$c = 1$和$n_0 = 0$）。因此，$t(n) \in \Omega(n^2)$。

大$\Theta$符号($\Theta$-notation)

紧界。如果存在常数$c_1 > 0$，$c_2 > 0$和$n_0 \geq 0$，使得对于所有$n \geq n_0$，有$c_2 \cdot g(n) \leq t(n) \leq c_1 \cdot g(n)$，则$t(n)$是$\Theta(g(n))$。

例如，$t(n) = \frac{1}{2}n(n-1)$，证明$t(n) \in \Theta(n^2)$：

证明：对于所有$n \geq 0$，有$\frac{1}{2}n(n-1) = \frac{1}{2}n^2 - \frac{1}{2}n \leq \frac{1}{2}n^2$（上界）。对于所有$n \geq 2$，有$\frac{1}{2}n(n-1) = \frac{1}{2}n^2 - \frac{1}{2}n \geq \frac{1}{2}n^2 - \frac{1}{2}n \geq \frac{1}{4}n^2$（下界）（即取$c_2 = \frac{1}{4}$，$c_1 = \frac{1}{2}$和$n_0 = 2$）。因此，$t(n) \in \Theta(n^2)$。

基本渐近效率类

性质

传递性：

• 如果$f \in O(g)$且$g \in O(h)$，则$f \in O(h)$。
• 如果$f \in \Omega(g)$且$g \in \Omega(h)$，则$f \in \Omega(h)$。
• 如果$f \in \Theta(g)$且$g \in \Theta(h)$，则$f \in \Theta(h)$。

可加性：

• 如果$f \in O(h)$且$g \in O(h)$，则$f + g \in O(h)$。
  • 如果$f \in \Omega(h)$且$g \in \Omega(h)$，则$f + g \in \Omega(h)$。
• 如果$f \in \Theta(h)$且$g \in \Theta(h)$，则$f + g \in \Theta(h)$。

如果$f_1(n) \in O(g_1(n))$且$f_2(n) \in O(g_2(n))$，则$f_1(n) + f_2(n) \in O(\max(g_1(n), g_2(n)))$。

如果$f_1(n) \in \Omega(g_1(n))$且$f_2(n) \in \Omega(g_2(n))$，则$f_1(n) + f_2(n) \in \Omega(\max(g_1(n), g_2(n)))$。

如果$f_1(n) \in \Theta(g_1(n))$且$f_2(n) \in \Theta(g_2(n))$，则$f_1(n) + f_2(n) \in \Theta(\max(g_1(n), g_2(n)))$。

由两个依次执行的部分组成的算法的总体效率由具有更高增长阶数的部分决定（即其效率最低的部分）。

使用极限比较增长阶数

如果$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \begin{cases} 0, & \text{则} f(n) \in O(g(n)) \\ c, & \text{则} f(n) \in \Theta(g(n)) \text{且} f(n) \in O(g(n)) \text{且} f(n) \in \Omega(g(n)) \\ \infty, & \text{则} f(n) \in \Omega(g(n)) \end{cases}$

例如，比较$\frac{1}{2}n(n-1)$和$n^2$的增长阶数：

$\lim_{n \to \infty} \frac{\frac{1}{2}n(n-1)}{n^2} = \frac{1}{2} \lim_{n \to \infty} \frac{n^2-n}{n^2} = \frac{1}{2} \lim_{n \to \infty} (1 - \frac{1}{n}) = \frac{1}{2}$

因此，$\frac{1}{2}n(n-1) \in \Theta(n^2)$。

总结

• 时间效率：表示算法运行的速度
  • 输入规模的函数
  • 基本操作执行的次数
  • 最坏情况、平均情况、最佳情况
• 渐近增长阶数
  • $O$、$\Omega$、$\Theta$表示法
• 效率类别
  • 常数级(Constant)、对数级(Logarithmic)、线性级(Linear)、线性对数级(Linearithmic)、平方级(Quadratic)、立方级(Cubic)、指数级(Exponential)