5.3 步数统计与渐近增长

第 5.2 节证明算法是否正确。但正确性只能说明答案对不对，不能说明输入变大后算法是否仍然实用。

假设两个正确搜索过程在规模为 $n$ 的输入上分别需要

20n \qquad\text{与}\qquad n^2

次基本操作。当 $n=5$ 时，第二个表达式更小：

20(5)=100,\qquad5^2=25.

当 $n=100$ 时，比较结果反转：

20(100)=2000,\qquad100^2=10000.

为了理解可扩展性，我们要研究工作量怎样随输入规模增长。

输入规模与代价模型

输入规模是描述算法接收多少输入的数，通常记作 $n$ 。

例如：

对数组， $n$ 可以表示元素个数；

对图，规模可能同时涉及顶点数与边数；

对一个整数，规模可以指二进制位数，而不是整数本身的数值。

本节每次使用 $n$ 时都会说明它的含义。

代价模型规定要计算哪些基本操作，例如比较、赋值、算术运算或数组访问。

这个计数是数学模型，不是秒表测量。真实机器在处理器速度、语言、编译器和内存行为上都有差异。计算操作次数可以让我们不依赖这些细节比较算法。

计算直线式过程

考虑：

text

x ← a + b
y ← x × 2
return y

若计算算术操作与赋值，一种模型会得到：

一次加法；

一次给 $x$ 赋值；

一次乘法；

一次给 $y$ 赋值。

总计为 $4$ ，与输入规模无关。另一种合理模型可能计算 return，或者把算术与赋值视为一次组合操作。精确常数会变化，但“不随输入增长”这一点不变。

计算单层循环

考虑：

text

total ← 0
for i ← 1 to n
    total ← total + A[i]
return total

如果只计算循环体中加法的执行次数，精确计数是

T(n)=n.

如果计算一次初始化、 $n$ 次加法、 $n$ 次给 $total$ 赋值和一次返回，则

T(n)=1+n+n+1=2n+2.

代价模型改变精确公式，但两个公式都与 $n$ 成比例增长。

顺序代码块相加

如果一个循环运行 $n$ 次，后面的另一个循环运行 $3n$ 次，循环体总执行次数为

n+3n=4n.

因为第二块在第一块之后运行，所以顺序工作量相加。

嵌套循环相乘

考虑：

text

for i ← 1 to n
    for j ← 1 to n
        output (i, j)

对 $i$ 的每个取值，内层循环都会使用 $j$ 的全部 $n$ 个取值。因此 output 执行

\underbrace{n+n+\cdots+n}_{n\text{ 项}}=n^2

次。

这些迭代对应笛卡尔积

\{1,\ldots,n\}\times\{1,\ldots,n\},

这与第 1 章建立了联系。

并非每个嵌套循环都是 $n^2$ 。如果内层循环只从 $1$ 运行到 $i$ ，计数为

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

它仍然是二次增长，但精确数量大约只有 $n^2$ 的一半。

每次减半的循环

考虑：

text

x ← n
while x > 1
    x ← floor(x / 2)

执行 $k$ 次后， $x$ 大约为

\frac{n}{2^k}.

当这个值到达 $1$ 时循环停止。解不等式

\frac{n}{2^k}\le1

得到

n\le2^k \qquad\Longrightarrow\qquad k\ge\log_2 n.

在许多常见边界约定下，迭代次数为

\lfloor\log_2 n\rfloor,

至多相差一个小的端点调整。重要结论是对数增长：把 $n$ 加倍，迭代次数大约只增加一次。

正在加载交互实验...

在实时操作计数器下运行单层、顺序、嵌套、三角形与减半循环。改变 $n$ ，逐步观察被高亮的执行位置，再把实际轨迹与从可视迭代区域拼出的精确符号计数进行比较。

正在加载概念检查...

正在加载本节练习...

最好情况与最坏情况

同一个输入规模可能产生不同代价。

对长度为 $n$ 的数组进行线性搜索：

如果目标在索引 $0$ ，一次比较就足够；

如果目标不存在，或只出现在索引 $n-1$ ，算法要做 $n$ 次比较。

因此：

T_{\mathrm{best}}(n)=1, \qquad T_{\mathrm{worst}}(n)=n.

每次陈述复杂度时，都应说明它描述最好情况、最坏情况还是其他指定情形。本课程中，如果没有额外说明，上界分析通常指最坏情况。

为什么有时不需要精确公式的全部细节

假设一个实现使用

T_1(n)=3n^2+10n+7,

另一个使用

T_2(n)=50n^2+2.

精确计数不同，但当 $n$ 很大时，二者都被 $n^2$ 的常数倍控制。二次项最终增长得比线性项与常数项更快。

渐近分析描述这种长期增长，并忽略常数因子与低阶项。

大 O 给出最终上界

如果存在常数 $c>0$ 与 $n_0$ ，使得对每个 $n\ge n_0$ 都有

0\le f(n)\le c\,g(n),

就写成

f(n)\in O(g(n)).

常数 $c,n_0$ 是见证。不等式不必对每个小输入成立，只需要从某个阈值以后一直成立。

示例：证明二次上界

令

f(n)=3n^2+10n+7.

当 $n\ge1$ 时，

10n\le10n^2 \qquad\text{且}\qquad 7\le7n^2.

因此

f(n) \le3n^2+10n^2+7n^2 =20n^2.

选择 $c=20,n_0=1$ 就证明

f(n)\in O(n^2).

大 O 是上界，不一定是紧确描述。因为当 $n\ge1$ 时 $n\le n^2$ ，线性函数也属于 $O(n^2)$ 。要表达“恰好按这个阶增长”，需要匹配的上界与下界。

大 Omega 给出最终下界

如果存在常数 $c>0$ 与 $n_0$ ，使得对每个 $n\ge n_0$ 都有

0\le c\,g(n)\le f(n),

就写成

f(n)\in\Omega(g(n)).

对 $f(n)=3n^2+10n+7$ 且 $n\ge1$ ，

3n^2\le f(n),

所以取 $c=3$ 得到 $f(n)\in\Omega(n^2)$ 。

大 Theta 给出紧确增长率

当

f(n)\in O(g(n)) \qquad\text{且}\qquad f(n)\in\Omega(g(n))

同时成立时，写成

f(n)\in\Theta(g(n)).

等价地，存在正数 $c_1,c_2,n_0$ ，使对每个 $n\ge n_0$ ，

0\le c_1g(n)\le f(n)\le c_2g(n).

前面的两个界证明了

3n^2+10n+7\in\Theta(n^2).

常见增长函数族

从慢到快，常见非负增长率为：

1 \prec \log n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!.

这里的 $\prec$ 非正式表示“最终增长得更慢”。它不是第 4 章的偏序关系，虽然二者都表达比较。

增长差距会变得非常夸张。当 $n=20$ 时：

n^2=400, \qquad 2^n=1{,}048{,}576, \qquad n!=2{,}432{,}902{,}008{,}176{,}640{,}000.

常数对真实工作负载仍然重要，尤其在输入较小时。渐近增长回答的是另一个问题：如果输入规模继续增加，会发生什么？

正在加载交互实验...

把带有可调常数因子的函数发射到对数增长赛道。移动输入规模地平线，观察交叉点，并拟合上下包络，从而区分宽松的大 O 陈述与紧确的大 Theta 分类。

正在加载概念检查...

正在加载本节练习...

注意

大 O 本身既不表示“等于”，也不自动表示“最坏情况”。它是一种最终上界关系。输入情形要另行说明；当上下界匹配时，应使用大 Theta。

本章衔接

第 5 章把过程与数学连接起来。我们用伪代码描述算法，用不变量与终止度量证明正确性，计算精确操作次数，并分类长期增长。

第 6 章将发展系统计数原理。这些工具让我们不必逐项列举就能计算选择数量，也会解释嵌套循环、搜索空间和组合算法为什么会增长得如此迅速。

5.3 步数统计与渐近增长

第 5.2 节证明算法是否正确。但正确性只能说明答案对不对，不能说明输入变大后算法是否仍然实用。

假设两个正确搜索过程在规模为 $n$ 的输入上分别需要

20n \qquad\text{与}\qquad n^2

次基本操作。当 $n=5$ 时，第二个表达式更小：

20(5)=100,\qquad5^2=25.

当 $n=100$ 时，比较结果反转：

20(100)=2000,\qquad100^2=10000.

为了理解可扩展性，我们要研究工作量怎样随输入规模增长。

输入规模与代价模型

输入规模是描述算法接收多少输入的数，通常记作 $n$ 。

例如：

对数组， $n$ 可以表示元素个数；

对图，规模可能同时涉及顶点数与边数；

对一个整数，规模可以指二进制位数，而不是整数本身的数值。

本节每次使用 $n$ 时都会说明它的含义。

代价模型规定要计算哪些基本操作，例如比较、赋值、算术运算或数组访问。

计算直线式过程

考虑：

text

x ← a + b
y ← x × 2
return y

若计算算术操作与赋值，一种模型会得到：

一次加法；

一次给 $x$ 赋值；

一次乘法；

一次给 $y$ 赋值。

计算单层循环

考虑：

text

total ← 0
for i ← 1 to n
    total ← total + A[i]
return total

如果只计算循环体中加法的执行次数，精确计数是

T(n)=n.

如果计算一次初始化、 $n$ 次加法、 $n$ 次给 $total$ 赋值和一次返回，则

T(n)=1+n+n+1=2n+2.

代价模型改变精确公式，但两个公式都与 $n$ 成比例增长。

顺序代码块相加

如果一个循环运行 $n$ 次，后面的另一个循环运行 $3n$ 次，循环体总执行次数为

n+3n=4n.

因为第二块在第一块之后运行，所以顺序工作量相加。

嵌套循环相乘

考虑：

text

for i ← 1 to n
    for j ← 1 to n
        output (i, j)

对 $i$ 的每个取值，内层循环都会使用 $j$ 的全部 $n$ 个取值。因此 output 执行

\underbrace{n+n+\cdots+n}_{n\text{ 项}}=n^2

次。

这些迭代对应笛卡尔积

\{1,\ldots,n\}\times\{1,\ldots,n\},

这与第 1 章建立了联系。

并非每个嵌套循环都是 $n^2$ 。如果内层循环只从 $1$ 运行到 $i$ ，计数为

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

它仍然是二次增长，但精确数量大约只有 $n^2$ 的一半。

每次减半的循环

考虑：

text

x ← n
while x > 1
    x ← floor(x / 2)

执行 $k$ 次后， $x$ 大约为

\frac{n}{2^k}.

当这个值到达 $1$ 时循环停止。解不等式

\frac{n}{2^k}\le1

得到

n\le2^k \qquad\Longrightarrow\qquad k\ge\log_2 n.

在许多常见边界约定下，迭代次数为

\lfloor\log_2 n\rfloor,

至多相差一个小的端点调整。重要结论是对数增长：把 $n$ 加倍，迭代次数大约只增加一次。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

最好情况与最坏情况

同一个输入规模可能产生不同代价。

对长度为 $n$ 的数组进行线性搜索：

如果目标在索引 $0$ ，一次比较就足够；

如果目标不存在，或只出现在索引 $n-1$ ，算法要做 $n$ 次比较。

因此：

T_{\mathrm{best}}(n)=1, \qquad T_{\mathrm{worst}}(n)=n.

每次陈述复杂度时，都应说明它描述最好情况、最坏情况还是其他指定情形。本课程中，如果没有额外说明，上界分析通常指最坏情况。

为什么有时不需要精确公式的全部细节

假设一个实现使用

T_1(n)=3n^2+10n+7,

另一个使用

T_2(n)=50n^2+2.

精确计数不同，但当 $n$ 很大时，二者都被 $n^2$ 的常数倍控制。二次项最终增长得比线性项与常数项更快。

渐近分析描述这种长期增长，并忽略常数因子与低阶项。

大 O 给出最终上界

如果存在常数 $c>0$ 与 $n_0$ ，使得对每个 $n\ge n_0$ 都有

0\le f(n)\le c\,g(n),

就写成

f(n)\in O(g(n)).

常数 $c,n_0$ 是见证。不等式不必对每个小输入成立，只需要从某个阈值以后一直成立。

示例：证明二次上界

令

f(n)=3n^2+10n+7.

当 $n\ge1$ 时，

10n\le10n^2 \qquad\text{且}\qquad 7\le7n^2.

因此

f(n) \le3n^2+10n^2+7n^2 =20n^2.

选择 $c=20,n_0=1$ 就证明

f(n)\in O(n^2).

大 O 是上界，不一定是紧确描述。因为当 $n\ge1$ 时 $n\le n^2$ ，线性函数也属于 $O(n^2)$ 。要表达“恰好按这个阶增长”，需要匹配的上界与下界。

大 Omega 给出最终下界

如果存在常数 $c>0$ 与 $n_0$ ，使得对每个 $n\ge n_0$ 都有

0\le c\,g(n)\le f(n),

就写成

f(n)\in\Omega(g(n)).

对 $f(n)=3n^2+10n+7$ 且 $n\ge1$ ，

3n^2\le f(n),

所以取 $c=3$ 得到 $f(n)\in\Omega(n^2)$ 。

大 Theta 给出紧确增长率

当

f(n)\in O(g(n)) \qquad\text{且}\qquad f(n)\in\Omega(g(n))

同时成立时，写成

f(n)\in\Theta(g(n)).

等价地，存在正数 $c_1,c_2,n_0$ ，使对每个 $n\ge n_0$ ，

0\le c_1g(n)\le f(n)\le c_2g(n).

前面的两个界证明了

3n^2+10n+7\in\Theta(n^2).

常见增长函数族

从慢到快，常见非负增长率为：

1 \prec \log n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!.

这里的 $\prec$ 非正式表示“最终增长得更慢”。它不是第 4 章的偏序关系，虽然二者都表达比较。

增长差距会变得非常夸张。当 $n=20$ 时：

n^2=400, \qquad 2^n=1{,}048{,}576, \qquad n!=2{,}432{,}902{,}008{,}176{,}640{,}000.

常数对真实工作负载仍然重要，尤其在输入较小时。渐近增长回答的是另一个问题：如果输入规模继续增加，会发生什么？

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

大 O 本身既不表示“等于”，也不自动表示“最坏情况”。它是一种最终上界关系。输入情形要另行说明；当上下界匹配时，应使用大 Theta。

本章衔接

第 5 章把过程与数学连接起来。我们用伪代码描述算法，用不变量与终止度量证明正确性，计算精确操作次数，并分类长期增长。

第 6 章将发展系统计数原理。这些工具让我们不必逐项列举就能计算选择数量，也会解释嵌套循环、搜索空间和组合算法为什么会增长得如此迅速。