1.2 算法与复杂度分析

算法的五个特性与评价标准，学会用大 O 记号分析时间复杂度与空间复杂度。

什么是算法

一个算法必须具备以下五个特性：

“好”的算法应达到以下目标：正确性、可读性、健壮性（对非法输入能做出适当反应）、高效率与低存储量需求。其中效率和存储量，就是用时间复杂度和空间复杂度来度量的。

时间复杂度

从”语句频度”到”渐近记号”

一条语句的频度是指它在算法中被重复执行的次数。算法中所有语句频度之和记为 $T(n)$，它是问题规模 $n$ 的函数。

我们并不关心 $T(n)$ 的精确值，而是关心当 $n \to \infty$ 时它的增长趋势。通常只需考察基本运算（最深层循环内的语句）的频度 $f(n)$，并取其数量级：

其数学含义是：存在正常数 $C$ 和 $n_0$，使得当 $n \ge n_0$ 时都满足 $0 \le T(n) \le C \cdot f(n)$。也就是说，$O$ 给出的是增长率的上界。

两条运算规则

• 加法规则：$T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))$ —— 顺序执行的代码，取最大的那部分。
• 乘法规则：$T(n) = T_1(n) \times T_2(n) = O(f(n)) \times O(g(n)) = O(f(n) \times g(n))$ —— 嵌套的代码，复杂度相乘。

常见复杂度的比较

拖动下面的滑块，直观感受它们的增长速度差异。勾选”对数纵轴”可以同时观察指数阶与多项式阶：

最坏、平均与最好情况

同一个算法，对不同的输入实例，执行次数可能不同。例如在数组中顺序查找值 x：

• 最好时间复杂度：x 恰好在第一个位置，$O(1)$；
• 最坏时间复杂度：x 在最后或不存在，$O(n)$；
• 平均时间复杂度：所有输入等概率出现时的期望，约 $(n+1)/2$ 次比较，$O(n)$。

动手分析：数一数执行次数

分析循环程序的通用方法：设基本语句执行了 $t$ 次，找出循环变量与 $t$ 的关系，再由循环结束条件解出 $t$。

下面的动画会真实地”运行”四段经典代码，每执行一次基本语句就画一个方块。切换代码和 $n$ 的值，观察次数的增长规律：

1int count = 0;
2for (int i = 1; i <= n; i *= 2)
3    count++;          // 基本语句

对照动画，我们把四种模式整理成”套路”：

模式 1：循环变量倍增

for (i = 1; i <= n; i *= 2)
    count++;

设执行 $t$ 次，则第 $t$ 次时 $i = 2^{t-1} \le n$，得 $t \le \log_2 n + 1$，所以 $T(n) = O(\log_2 n)$。

模式 2：内层循环次数依赖外层变量

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        count++;

模式 3：外层倍增、内层随之增长（易错！）

for (i = 1; i <= n; i *= 2)
    for (j = 1; j <= i; j++)
        count++;

很多同学会想”外层 $\log n$ 次 × 内层 $n$ 次 = $O(n\log n)$“——错！内层次数是 $i$，而 $i$ 取 $1, 2, 4, \ldots, 2^k$（$2^k \le n$），因此

模式 4：累加直到超过 n

i = 0; s = 0;
while (s < n) { i++; s = s + i; }

执行 $t$ 次后 $s = 1 + 2 + \cdots + t = t(t+1)/2$，令其 $\ge n$，得 $t \approx \sqrt{2n}$，故 $T(n) = O(\sqrt{n})$。

同理，while (i * i <= n) i++; 的复杂度也是 $O(\sqrt n)$。

递归程序的时间复杂度

递归算法的分析通常先写出递推式，再展开求解。例如求阶乘：

int fact(int n) {
    if (n <= 1) return 1;       // 递归出口
    return n * fact(n - 1);     // 规模减 1
}

$T(n) = T(n-1) + O(1)$，展开得 $T(n) = T(1) + (n-1) \cdot O(1) = O(n)$。

再如归并排序：$T(n) = 2T(n/2) + O(n)$，展开 $\log_2 n$ 层，每层合计 $O(n)$，故 $T(n) = O(n\log_2 n)$。

空间复杂度

算法的空间复杂度 $S(n)$ 定义为该算法所需的存储空间，也是问题规模 $n$ 的函数：$S(n) = O(g(n))$。

• 只考虑除输入数据本身以外的辅助空间。
• 若算法所需辅助空间为常数，即 $O(1)$，称算法原地工作（in-place）。
• 递归程序要计入递归工作栈的深度：例如上面的 fact(n) 递归深度为 $n$，空间复杂度为 $O(n)$。

即时练习