分析算法

分析算法(Algorithm Analysis) 是计算机科学中研究算法效率与资源消耗的学科, 旨在评估算法在不同输入规模下的性能表现, 为选择和优化算法提供理论依据. 其核心目标是回答两个关键问题:

• 时间效率: 算法执行需要多少时间？
• 空间效率: 算法运行需要多少内存或其他资源？

RAM模型

《算法导论》介绍了一种 RAM模型(Random Access Machine, 随机存取机). 它是计算机科学中用于分析算法时间复杂度的一种抽象计算模型. 它简化了真实计算机的复杂性, 假设所有基本操作(如算术运算、内存访问等)均可在常数时间内完成, 从而聚焦于算法本身的逻辑效率.

核心特点

1. 随机访问内存

   • 假设内存是“扁平化“的, 访问任意地址的数据耗时相同(与硬盘的顺序访问不同).
   • 例如, 读取 A[i] 和 A[j] 的时间相同, 无论 i 和 j 的距离多远.

2. 基本操作耗时恒定

   • 算术运算(+, -, *, /)
   • 逻辑比较(>, ==, &&)
   • 内存读写(赋值、访问变量)
   • 控制流(if, for, return等)

以上操作均视为常数时间操作.

3. 单处理器、无并发

   • 假设程序按顺序执行, 不考虑多线程、缓存或并行计算的影响.

4. 无限内存(理想化)

   • 忽略物理内存限制, 但实际分析中仍需考虑空间复杂度.

为什么使用RAM模型？

• 简化分析: 屏蔽硬件差异(如CPU速度、缓存层次), 专注于算法的渐进复杂度.
• 通用性: 适用于大多数传统算法(排序、搜索、动态规划等).
• 理论基准: 与图灵机等价, 但更贴近编程实践.

用RAM模型进行严格的算法分析是较难的, 需要的数学技巧和工具很多. 如:

#![allow(unused)]
fn main() {
pub fn insert_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}
}

我们以 $c_i$ 表示每个操作的代价.

#![allow(unused)]
fn main() {
pub fn insert_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {                     // 代价: c_1
        let mut j = i;                          // 代价: c_2
        while j > 0 && arr[j] < arr[j - 1] {    // 代价: c_3
            arr.swap(j, j - 1);                 // 代价: c_4
            j -= 1;                             // 代价: c_5
        }
    }
}
}

Note

下面要使用求和知识, 可参见 附录.

每个代价在循环条件都有不同次数的消耗, 通过数学分析可以得到:

#![allow(unused)]
fn main() {
// 先给定 n = arr.len()
pub fn insert_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {                     // 次数: n - 1
        let mut j = i;                          // 次数: n - 1
        // 考虑到下面的评估次数受到数组的实际影响, 我们简单表达:
        // 设 t_i 为本次内循环中while条件的评估次数
        // 要注意: 内循环的评估次数并不代表消耗次数, 因为其要受到外循环的影响
        while j > 0 && arr[j] < arr[j - 1] {    // 次数: \sum_{i=1}^{n-1} t_i
            arr.swap(j, j - 1);                 // 次数: \sum_{i=1}^{n-1} (t_i - 1)
            j -= 1;                             // 次数: \sum_{i=1}^{n-1} (t_i - 1)
        }
        // 注: t_i在最优情况下为1(数组已排序), 在最坏情况下为i+1(数组恰为倒序排序)
    }
}
}

每一步操作的实际消耗是代价乘上对应的次数, 我们用 $T$ 代表一个算法(或操作)的运行时间, 同时对这种形式我们加之 n 等参数使表示更为精准($t_i$对于输入情况的解释非常复杂), 那么有: $$\begin{array}{rl}T(n)& =c_1(n-1)+c_2(n-1)+c_3\left(\sum _{i=1}^{n-1}{t}_i\right)\\ & +c_4\left(\sum _{i=1}^{n-1}(t_i-1)\right)+c_5\left(\sum _{i=1}^{n-1}(t_i-1)\right)\end{array}$$

接着我们代入t_i最值, 于是有:

最优情况: $$\begin{array}{rl}T(n)& =c_1(n-1)+c_2(n-1)+c_3(n-1)\\ & =(c_1+c_2+c_3)n+(c_1+c_2+c_3)\end{array}$$ 观察后可以发现, $c_i$属于基本操作, 所以 $(c_1+c_2+c_3)$ 是常数, 不难得 $T(n)$ 是关于 $n$ 的线性函数¹.

最坏情况:

最坏情况下, 注意到 $$\sum _{i=1}^{n-1}{t}_i=\sum _{i=1}^{n-1}(i+1)=\frac{n(n+1)}{2}-1$$ 和 $$\sum _{i=1}^{n-1}(t_i-1)=\sum _{i=1}^{n-1}i=\frac{n(n-1)}{2}$$ 同样我们代入变形: $$\begin{array}{rl}T(n)& =\frac{c_3+c_4+c_5}{2}{n}^2+\left(c_1+c_2+\frac{c_3-c_4-c_5}{2}\right)n\\ & -\left(c_1+c_2+c_3-\frac{c_4+c_5}{2}\right)\end{array}$$ 很显然, 这是一个二次函数.

在分析插入排序时, 我们既研究了最佳情况, 其中输入数组已排好序, 又研究了最坏情况, 其中输入数组已反向排好序. 然而, 在本书的余下部分中, 我们往往集中于只求最坏情况运行时间, 即对规模为n的任何输入, 算法的最长运行时间. 下面给出这样做的三点理由:

• 一个算法的最坏情况运行时间给出了任何输入的运行时间的一个上界. 知道了这个界, 就能确保该算法绝不需要更长的时间. 我们不必对运行时间做某种复杂的猜测并可以期望它不会变得更坏.
• 对某些算法, 最坏情况经常出现. 例如, 当在数据库中检索一条特定信息时, 若该信息不在数据库中出现, 则检索算法的最坏情况会经常出现. 在某些应用中, 对缺失信息的检索可能是频繁的.
• “平均情况“往往与最坏情况大致一样差. 例如上例, 假令输入为一半排序一半逆序, 分析之后同样是一个二次函数.

在某些情况下, 平均情况与最坏情况还是有较大差别的(事实上, 对于大部分算法, 我们并不明确什么是平均情况, 有时候需要大量的概率分析来进行评估), 同时对于随机情况的出现也并不明确, 我们将在后面的内容探讨这些. 但首先我们要对这些算法的增长情况进行简单描述:

增长量级

对于像上面这个二次函数, 数据较大时, 常数项和一次项对增长率的影响不大, 所以我们忽略这些内容之后只剩下最重要的$n^2$. 我们记插入排序的一般时间复杂度(抽象运行时间)为$\Theta (n^3)$. $\Theta$²一般用来指代平均情况, 它的值介于最坏情况和最优情况之间. 这通常意味着存在输入使得运行时间达到且所有输入的最坏时间不超过. 相当于在最坏情况下, 运行时间恰好是$\Theta$所描述的. 在很多课本中我们使用$O$来描述, 这其实没有$\Theta$精准, $O$代表着运行时间的上界, 但不一定存在一个输入能达到这个上界, $\Theta$则必然存在. 关于$\Theta$的严格定义将在后面讲到.

增长量级其实是一类数学问题, 量化了函数在无穷远处的增长行为.

在后面的内容中, 我们非形式化的使用$\Theta$. ³

练习与回答

1. 用$\Theta$记号表示函数$f(n)=\frac{n^3}{1000}-100n^2-100n+3$.

在这里我们不采用严格的数学证明.

记住最高阶项决定一切, 忽视系数和低次项直接得到答案——$\Theta (n^3)$.

2. 考虑排序存储在数组A中的n个数: 首先找出A中的最小元素并将其与A[1]中的元素进行交换. 接着, 找出A中的次最小元素并将其与A[2]中的元素进行交换. 对A中前n-1个元素按该方式继续. 该算法称为选择排序算法.
   1. 写出其Rust代码.
   2. 该算法维持的循环不变式是什么？
   3. 为什么只需要对前n-1个元素, 而不是对所有n个元素运行？
   4. 用$\Theta$记号给出选择排序的最好情况与最坏情况运行时间.

1. Rust代码

#![allow(unused)]
fn main() {
pub fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n - 1 { // 只需遍历前 n-1 个元素
        let mut min_index = i;
        for j in i + 1..n { // 在剩余部分中寻找最小元素
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        if min_index != i { // 交换当前元素与最小元素
            arr.swap(i, min_index);
        }
    }
}
}

2. 循环不变式

在每次外层循环开始时, 子数组A[0..i]已经是有序的, 并且其中的所有元素 ≤ 子数组A[i..n]中的元素.

3. 为什么只需对前n-1个元素运行

数学原因

当对前n-1个元素排序后, 最后一个元素A[n-1]必然是剩余子数组A[n-1..n]的最小也是唯一的元素, 因此整个数组已经有序.

算法效率

减少一次不必要的遍历, 但时间复杂度不变.

4. 时间复杂度分析

$$\sum _{i=0}^{n-2}(n-1-i)=\frac{n(n+1)}{2}=\Theta (n^2)$$ 选择排序的时间复杂度在所有情况下均为$\Theta (n^2)$.

3. 再次考虑线性查找问题(参见这里). 用$\Theta$记号给出线性查找的平均情况和最坏情况运行时间.

最坏情况比较简单: $$T_{\text{worst}}(n)=\Theta (n)$$ 平均情况要分析:

假设目标元素一定存在于数组中, 且出现在每个位置的概率均等即($P(v=A[i])=\frac{1}{n}$).

比较次数的期望值: $$\begin{array}{rl}E& =\sum _{k=1}^n\left(\text{第 }k\text{ 次找到的概率}\times k\right)\\ & =\sum _{k=1}^n\left(\frac{1}{n}\times k\right)=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}\end{array}$$

则

$$T_{\text{avg}}(n)=\Theta (n)$$

1. 这里的线性函数并不是高等数学中的严格定义. 《算法导论》中, 使用的是初等数学中的宽松定义(即形如 $f(x)=kx+b(k\ne 0)$ 的一次函数). 对于高等数学来说, 上面的函数既不满足齐次性, 又不满足叠加性(当$(c_1+c_2+c_3)$为0时, 原函数变化成零函数, 满足线性要求, 但显然不为0). 由于$b=c_1+c_2+c_3\ne 0$所以该函数更准确的叫仿射函数. ↩

2. 希腊语中的第8个字母, 读作 theta. ↩

3. 时间复杂度(Time Complexity) 描述算法执行时间随输入规模增长的变化趋势. 运行时间(Running Time) 描述算法在特定输入下实际消耗的时间. 在本章之后, 我们正式将二者区分. ↩