3.1 复杂度增长与算法成本

动机

“程序 A 更快”并不是完整结论：必须说明输入规模、计费操作、合法输入及所讨论的情形。课件以选择排序为动机；某台机器的测量显示，数组规模加倍时，时间约增至四倍。这能说明增长趋势，却不是证明，因为硬件、编译器、存储行为与有限规模的常数都会影响计时。

复杂度分析改问数学问题。先定义成本函数 $T(n)$ ，再计算基本操作次数，最后研究 $n$ 增大时的变化。结论依赖模型：固定长度键的比较可视为常数时间，任意长字符串的比较则未必如此。本节要求先写精确计数或可验证的界，再给出紧确的渐近类别，而不是凭循环层数猜答案。

定义

输入规模与 RAM 成本模型

对输入 $I$ ，令 $n=|I|$ 为明确声明的规模， $T(I)$ 为被计费的基本操作数。除非另有说明，本节采用单位成本 RAM 模型：固定字长算术、索引运算、数组访问、赋值及固定长度键比较均为常数成本。 $T(n)$ 还须注明情形；例如最坏成本是在所有规模为 $n$ 的合法输入上取最大值。

时间与辅助空间是不同资源。辅助函数调用必须计入其完整成本，不能因为源代码只占一行便当作常数时间。

定义

渐近上界、下界与紧确界

设 $f,g:\mathbb N\to\mathbb R_{\ge0}$ 最终非负，且 $g$ 最终为正。

若存在 $C>0,n_0$ ，使所有 $n\ge n_0$ 都有 $f(n)\le Cg(n)$ ，则 $f(n)=O(g(n))$ ；
若存在 $c>0,n_0$ ，使所有 $n\ge n_0$ 都有 $f(n)\ge cg(n)$ ，则 $f(n)=\Omega(g(n))$ ；
若同时存在上下界，即 $cg(n)\le f(n)\le Cg(n)$ ，则 $f(n)=\Theta(g(n))$ 。

Big-O 只是最终上界，并非增长率的唯一名称。线性函数也属于 $O(n^2)$ ；要表达相同的紧确增长率，应使用 $\Theta$ 。

定义

情形、期望成本与摊还成本

最好与最坏成本分别在规模相同的合法输入上取最小、最大值。平均成本必须声明输入概率模型。摊还分析不假设随机输入，而是考察指定操作序列。例如，令一个初始为空的动态数组具有固定正初始容量；每当容量用尽，就按固定因子 $\rho>1$ 扩容，并采用一致的整数取整规则。对于只包含 $m$ 次 push 的序列，普通 push 收取常数成本，resize 时每复制一个元素收取一个单位。一次 resize push 可为 $\Theta(n)$ ，但整个序列的总成本为 $\Theta(m)$ ，故每次 push 的摊还成本为 $\Theta(1)$ 。

从代码推导成本函数

可靠的分析可以按照固定次序进行。首先声明合法输入与规模参数。数组程序常以长度为 $n$ ，图算法可能同时依赖 $|V|$ 与 $|E|$ ，数值算法则可能依赖输入的位数而不是数值本身。若把真正的双参数问题硬塞进一个符号，便可能隐藏决定成本的情形。

其次说明计费操作。选择排序适合计算键比较次数，因为循环边界使该次数不依赖输入排列。若赋值、配置、复制键值也很重要，就应分别计算，再按明确的成本模型合并。“循环成本是 $n$ ”仍不完整；还必须说明这 $n$ 次执行各自进行了什么工作。

然后先把控制流程翻译成算术，再作渐近化简。顺序程序块的成本相加；固定成本的循环体在矩形迭代空间中重复时形成乘积；内层边界随外层索引变化时形成求和；递归程序只有在递归调用的数量、子问题规模与非递归工作都已说明后，才可写出递推式。

最后，若要声称紧确类别，就必须同时给出上界与下界。只有上界时，结论可能故意很松；匹配的下界说明该增长对于指定实现与指定情形不可避免。这个推导流程也会暴露隐藏前提，例如随机访问是否为常数时间、键长度是否有界，以及辅助函数是否暗中做了一次完整扫描。

固定底数 $a,b>1$ 时， $\log_a n=\log_b n/\log_b a$ ，换底只改变常数。对固定参数 $p>0$ 、 $0<\varepsilon<q$ 、 $A>1$ ，增长层级可写为

1 \prec (\log n)^p \prec n^\varepsilon \prec n^q \prec A^n,

因为 $(\log n)^p/n^\varepsilon\to0$ 且 $n^q/A^n\to0$ 。这里比较的是函数比值或紧确类别，不能仅凭两个 Big-O 集合断言谁“更快”。

边读边试

在同一 n 比较渐进增长

这个工具现在把增长级别绑到具体程序形状上，让读者可以改变 n，并把当前示例与比较表对照。

选择算法形状

程序示例

for (int width = 1; width < n; width *= 2) {
  for (int i = 0; i < n; i += 2 * width) {
    merge_block(i, width);
  }
}

增长级别: O(n log n)

估计基本步数: 64.00

如何理解: 大约有 log n 轮，而每一轮仍然会处理线性数量的数据。

Class	Value at n=16
O(1)	1.00
O(log n)	4.00
O(n)	16.00
O(n log n)	64.00
O(n^2)	256.00

负责任地比较增长类别

增长层级描述的是最终趋势，并非每个有限输入上的实测时间。常数很小的二次实现可能在有限范围内快于线性实现，缓存与编译器也会改变交叉点。渐近记号刻意忽略这些固定常数，以便比较长期扩展性；实际工程判断仍应把渐近结论与目标输入范围内的测量结合起来。

当两个成本都有正的紧确界时，比值可以给出精确比较。若 $f(n)/g(n)\to0$ ，则 $f=o(g)$ ，即 $f$ 的阶严格小于 $g$ ；若比值趋于有限正数，两者属于同一个 $\Theta$ 类，但精确运行时间仍可不同；若比值无界增长，则 $f$ 的阶更大。这个方法比直接排列两个 Big-O 归属更安全，因为其中任一上界都可能并不紧确。

定理 / 命题

定理

正首项多项式由最高次项控制

设 $f(n)=\sum_{k=0}^{d}a_kn^k$ ，其中 $d$ 为非负整数，系数为固定实数， $a_d>0$ ，且 $f$ 最终非负，则 $f(n)=\Theta(n^d)$ 。

定理

选择排序的比较次数是三角形求和

对 $n\ge1$ 的随机访问数组，在每次键比较为 $\Theta(1)$ 的模型中，所示选择排序对每个输入都恰好执行 $\sum_{i=1}^{n-1}(n-i)=n(n-1)/2$ 次比较，因此时间为 $\Theta(n^2)$ 。条件交换最多执行 $n-1$ 次，不改变紧确界。

证明思路或证明

证明

最高次项定理的证明

若 $d=0$ ，则每个 $n$ 都有 $f(n)=a_0>0$ ，所以 $f(n)=\Theta(1)=\Theta(n^0)$ 。以下设 $d\ge1$ 。当 $n\ge1$ 时，每个 $n^k$ （ $k<d$ ）都不超过 $n^d$ ，故 $f(n)\le |f(n)|\le(a_d+\sum_{k<d}|a_k|)n^d$ 。另一方面， $n^k/n^d\to0$ ，所以存在阈值 $n_0$ ，使低次项绝对值之和不超过 $(a_d/2)n^d$ 。于是 $f(n)\ge(a_d/2)n^d$ 。同一正函数给出上下常数倍界，故 $f(n)=\Theta(n^d)$ 。固定系数、正首项与最终非负条件说明“删去低次项”不是可任意套用的代数规则。

证明

选择排序比较次数的证明

外层第 $0$ 轮比较 $n-1$ 次，第 $1$ 轮比较 $n-2$ 次，最后一轮比较一次。循环边界不依赖键的排列，因此已排序、逆序与任意输入的比较数相同：

(n-1)+(n-2)+\cdots+1 =\sum_{i=1}^{n-1}(n-i) =\frac{n(n-1)}2.

对 $n\ge2$ ，该值介于 $n^2/4$ 与 $n^2/2$ 之间，故比较数为 $\Theta(n^2)$ 。循环控制和至多线性次交换不会改变此界。

一般比较排序的 $\Omega(n\log n)$ 下界属于比较决策树模型，并假设任意可排序输入。其证明以及 quickselect、计数排序、基数排序的参数化分析留给后续排序笔记；本节只明确模型边界，不重复证明。

例题详解

例题

为什么 n^2 支配 n

比较相对大小： $n/n^2=1/n\to0$ 。这不是说线性项从精确公式中消失，而是说它相对 $n^2$ 越来越小；配合正首项即可得到紧确的 $\Theta(n^2)$ 结论。

例题

常数时间语句

int x = a + b;
int y = x * 2;
return y;

在固定字长 RAM 模型中，每句只执行一次，顺序相加仍为 $\Theta(1)$ 。若 a、b 是位数随输入增长的任意精度整数，就必须另计算术成本。

例题

线性扫描

int sum(const int a[], int n) {
   int total = 0;
   for (int i = 0; i < n; i++) {
      total += a[i];
   }
   return total;
}

循环体恰好执行 $n$ 次且每次为常数成本，所以总成本是 $an+b=\Theta(n)$ 。课件中的 Average 也是一次完整扫描加一次除法；调用它是 $\Theta(n)$ ，不能只按“一行函数调用”计费。

例题

嵌套循环产生二次成本

int countPairs(int n) {
   int c = 0;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         c++;
      }
   }
   return c;
}

这段代码的内句恰好执行 $n\cdot n$ 次，故为 $\Theta(n^2)$ ；依据是边界独立，不是“看见两层循环”。

函数调用也会隐藏乘法。课件的朴素方差程序在 $n$ 次循环中每次调用 $\Theta(n)$ 的 Average(array,n)，故主体为 $\Theta(n^2)$ ；末尾再扫描一次只加 $\Theta(n)$ 。把均值先算一次，多个顺序线性阶段相加便成为 $\Theta(n)$ 。若使用临时数组，还须另报辅助空间。

同一方法也适用于非矩形循环。如果内层从 i + 1 运行到 n - 1，执行次数是 $\sum_{i=0}^{n-2}(n-i-1)$ ，即三角形求和；如果索引每轮加倍，则由 $2^k<n$ 得到 $k=\Theta(\log n)$ ；如果内层上界为 i，就必须计算 $\sum_i i$ ，不能写成 $n$ 乘一个固定数。因此真正需要分析的是循环边界描述的迭代空间，而不是源代码中出现了多少个 for。

例题

选择排序的增长

void selectionSort(int a[], int n) {
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if (a[j] < a[min]) min = j;
      }
      if (min != i) {
         int tmp = a[i];
         a[i] = a[min];
         a[min] = tmp;
      }
   }
}

比较次数恰为 $n(n-1)/2$ 。把 $n$ 换成 $2n$ 或 $10n$ ，主导二次式的比值分别趋近 $4$ 与 $100$ 。这解释课件的计时趋势；真正证明类别的是计数定理，而非有限数据表。

例题

一个完整的化简证明

取 $C=1,n_0=1$ ，则所有 $n\ge1$ 都有

\frac{n^2+n}{2}\le\frac{n^2+n^2}{2}=n^2.

再由 $(n^2+n)/2\ge n^2/2$ 得到下界，所以紧确结论是 $\Theta(n^2)$ 。 $O(n^3)$ 虽也正确，却不够精确。

例题

二分查找不需要完整扫描

int binarySearch(const int a[], int n, int target) {
   int left = 0, right = n - 1;
   while (left <= right) {
      int mid = left + (right - left) / 2;
      if (a[mid] == target) return mid;
      if (a[mid] < target) left = mid + 1;
      else right = mid - 1;
   }
   return -1;
}

前提是已排序、可随机访问的数组，且键比较为常数时间。首次命中时最好成本为 $\Theta(1)$ ；最坏情况下每轮至多保留一半候选，故为 $\Theta(\log n)$ 。中点写法避免 left + right 溢出。

查找失败时仍有相同的对数最坏界：候选区间不断缩小，直到变空。若允许重复键，这个版本可返回任意一个匹配位置；寻找第一个或最后一个匹配位置需要修改循环不变量。二分查找也不会免费把未排序查找变成对数成本：预先排序的成本只有在可由足够多次后续查询共同承担时才划算。链表不能以常数时间定位中点，因此“随机访问”是复杂度结论的组成部分，而不是无关的实现细节。

例题

为什么合并式结构得到 n log n

若算法不断对半分解，并且每一递归层的总合并工作为 $\Theta(n)$ ，则共有 $\Theta(\log n)$ 层，总成本为 $\Theta(n\log n)$ 。等价地，对二次幂规模， $T(n)=2T(n/2)+\Theta(n)$ 有该解；一般规模的取整只改变常数。必须证明“每层线性”，分治形式本身并不保证此界。

逐层求和描述的是时间，不会自动给出空间界。若两个递归调用顺序完成，活动调用深度为 $\Theta(\log n)$ ，而合并用的临时存储仍可能达到 $\Theta(n)$ 。改变实现或并行执行可能改变空间轮廓，却不一定改变总工作量的递推式，所以必须始终明确正在界定哪一种资源。

常见错误

把 Big-O 当成紧确类别

$n$ 同时属于 $O(n)$ 与 $O(n^2)$ 。仅凭两个上界不能比较最终增长；应比较函数比值或先证明 $\Theta$ 界。

常见错误

数循环关键字而不数执行次数

两个独立的嵌套长度为 $n$ 的循环产生 $n^2$ 次；顺序循环相加，三角形边界要作求和，对半循环只有对数轮。先写计数式，再化简。

常见错误

忽略前提、辅助调用或情形标签

二分查找要求已排序输入；平均成本要求概率分布；函数调用贡献完整成本。结论必须注明输入、模型及最好、最坏、期望或摊还情形。

常见错误

把舍去低次项当成任意代数删除

低次项仍影响精确成本与有限规模。只有在固定系数及最终非负等条件下，经不等式或比值论证后，才能用主导项化简。

常见错误

声称每次动态数组 push 都是常数时间

触发扩容的一次 push 可为 $\Theta(n)$ 。几何扩容下，指定操作序列中每次 push 的摊还成本是 $\Theta(1)$ ；这不等于单次最坏成本为常数。

总结

先声明 $n$ 、计费操作、资源与输入情形；
$O$ 、 $\Omega$ 、 $\Theta$ 分别表示上界、下界与紧确界；
固定底数的对数仅差常数，固定正幂支配对数，固定底指数函数支配多项式；
顺序成本相加，独立重复工作相乘，依赖边界求和，递归写递推式或逐层计数；
选择排序恰好比较 $n(n-1)/2$ 次，在所述模型中为 $\Theta(n^2)$ 。

练习

思考检查

若两个彼此独立的嵌套循环都运行 n 次，总成本的紧确类别是什么？

假设循环体总会执行且成本为 $\Theta(1)$ 。

思考检查

为什么 Theta(n log n) 成本在 n 足够大时增长慢于 Theta(n^2)？

比较代表函数的比值。

思考检查

0.0001n^3 + n 的紧确渐近类别是什么？

使用正首项多项式定理，而不只说“删除低次项”。

思考检查

为什么选择排序每轮只放置一个元素，成本仍为二次？

计算逐轮缩短的内层比较次数。

答案与解答

解答 · 答案 1

循环体执行 $n\cdot n=n^2$ 次，因此在给定独立性与常数成本前提下，总成本为 $\Theta(n^2)$ 。

解答 · 答案 2

比值为 $(n\log n)/n^2=(\log n)/n\to0$ 。配合正的紧确界，二次成本最终增长更快。

解答 · 答案 3

首项系数为正，其余项次数更低，所以是 $\Theta(n^3)$ 。它也属于 $O(n^4)$ ，但后者不是紧确类别。

解答 · 引导解答 4

各轮比较 $(n-1),(n-2),\ldots,1$ 次，总和为 $n(n-1)/2=\Theta(n^2)$ ，且不依赖输入排列。每轮放置一个元素之前仍须扫描剩余后缀。

3.1 复杂度增长与算法成本

动机

定义

输入规模与 RAM 成本模型

渐近上界、下界与紧确界

情形、期望成本与摊还成本

从代码推导成本函数

在同一 n 比较渐进增长

负责任地比较增长类别

定理 / 命题

正首项多项式由最高次项控制

选择排序的比较次数是三角形求和

证明思路或证明

最高次项定理的证明

选择排序比较次数的证明

例题详解

为什么 n^2 支配 n

常数时间语句

线性扫描

嵌套循环产生二次成本

选择排序的增长

一个完整的化简证明

二分查找不需要完整扫描

为什么合并式结构得到 n log n

常见错误

把 Big-O 当成紧确类别

数循环关键字而不数执行次数

忽略前提、辅助调用或情形标签

把舍去低次项当成任意代数删除

声称每次动态数组 push 都是常数时间

总结

练习

若两个彼此独立的嵌套循环都运行 n 次，总成本的紧确类别是什么？

为什么 Theta(n log n) 成本在 n 足够大时增长慢于 Theta(n^2)？

0.0001n^3 + n 的紧确渐近类别是什么？

为什么选择排序每轮只放置一个元素，成本仍为二次？

答案与解答

先备知识

本单元重点词汇

本系列更多笔记