从运行时间到渐近记号：把算法效率说清楚

同一段程序，在十条数据上看不出差别，到了千万条数据时却可能完全是两回事。真正有用的算法分析，不是拿秒表测一次，也不是看到一层循环就立刻写出一个大 O。我们要先确定输入规模，选定计算模型，再把执行次数写成输入规模的函数，最后才讨论这个函数增长得有多快。

这套方法把机器、语言和某次测试造成的偶然差异暂时放到一边，回答一个更稳定的问题：当输入继续变大，资源消耗会按照什么速度增长？下面我们从“究竟在数什么”开始，一直走到五种渐近记号、常见函数的增长关系，以及如何从真实代码中得到复杂度。

算法分析究竟在测什么

分析算法，就是预测算法会消耗多少资源。资源可以是运行时间、额外内存、通信量，甚至某种昂贵操作的执行次数。大多数入门分析把运行时间放在首位，但同一套方法同样可以分析空间：先找出需要计数的基本操作，再把总数写成输入规模的函数。

先定义输入规模

输入规模不总是“数组长度”。选错规模，后面的式子即使算对了，也没有解释力。

• 排序数组时，通常用元素个数 $n$。
• 处理一个整数时，通常用它的二进制位数，而不是整数本身的数值。读取一个有 $b$ 位的整数，输入规模应写成 $b$。
• 处理图时，经常同时使用顶点数 $V$ 和边数 $E$。只写一个 $n$ 会掩盖稀疏图与稠密图的差别。
• 处理矩阵时，行数和列数可能需要分别记录。对于方阵，才常把两者统一写成 $n$。

所以，看到“这个算法是 $O(n)$”时，第一句追问应该是：这里的 $n$ 表示什么？

用一个足够朴素的计算模型

为了让分析尽量不依赖某台具体机器，我们通常假设程序运行在单处理器的随机访问模型上：指令按顺序执行；加减、比较、赋值、数组按下标访问和分支判断等基本操作各花常数时间；一个机器字足以保存数组下标。

这个模型不是说所有现实操作都一样快。它只把固定倍数差异藏进常数中。例如，加法和除法在真实处理器上的代价可能不同，但只要它们的代价不随 $n$ 增长，渐近分析就把两者都视为常数时间。

模型也有边界。不能把“排序整个数组”当成一条常数时间指令；不能假定一个机器字可以装下任意长整数；一般也不能把任意实数的幂运算看成常数时间。缓存、虚拟内存和并行执行可能显著影响实测性能，但它们不在这个简化模型里。遇到缓存敏感、外存或并行问题时，需要换用更贴近目标系统的模型。

运行时间是执行次数的和

设第 $i$ 类基本操作每次花费常数 $c_i$，在输入 $x$ 上执行 $a_i(x)$ 次，那么运行时间可以写成：

对给定输入，$T(x)$ 通常是确定的；但两个规模同为 $n$ 的输入，内容不同，运行时间可能不同。已经有序的数组与逆序数组长度相同，插入排序的移动次数却差很多。因此，分析不能只写 $T(n)$ 就假装同规模输入都一样，还要说明讨论的是最好情形、最坏情形、平均情形，还是某个具体输入。

时间与空间是两张账

一条语句执行 $n$ 次，时间通常会累加 $n$ 次；空间却不一定。循环反复使用同一个变量，执行次数是 $n$，额外空间仍可能是常数。反过来，递归调用可能没有显式数组，却会在调用栈上保留多个活动记录。

分析空间时，应说明统计的是总存储量还是除输入外的额外空间。原地算法常用“额外空间 $O(1)$”描述，但这不代表输入本身不占空间。

从逐行计数走到增长阶

抽象不是一开始就把所有细节删掉。更可靠的顺序是：先把关键语句执行多少次算清楚，再观察哪些细节在大规模输入下不再决定增长速度。

用插入过程看同规模输入的差异

考虑下面的插入过程。外层依次处理位置 $j$，内层把当前元素向左移动到正确位置：

对 j 从 2 到 n：
    保存当前位置的元素
    从 j - 1 向左比较
    只要左侧元素更大，就把它右移一格
    把保存的元素放入空出的位置

外层循环会进行 $n-1$ 轮，但内层每轮的次数取决于输入内容。令 $t_j$ 表示第 $j$ 轮条件测试的次数，总时间由固定的外层工作与这些 $t_j$ 的和组成。

如果数组已经有序，每轮第一次比较就停止，$t_j$ 是常数。因此：

如果数组逆序，第 $j$ 个元素要跨过前面的 $j-1$ 个元素。移动总数是：

把比较、移动、赋值等常数成本全部合并，最坏情形可以写成一个二次函数：

最坏情形、平均情形与期望时间

最坏情形是在所有规模为 $n$ 的输入中取运行时间最大值：

它给出一项保证：任何规模为 $n$ 的输入都不会比这个界更慢。数据库查找中，“目标不存在”可能就会触发完整扫描，而且这种输入并不一定罕见。

平均情形不能凭感觉说“通常走一半”。必须先给规模为 $n$ 的输入定义概率分布。若输入 $x$ 出现的概率为 $P(x)$，平均运行时间是：

对插入排序，如果假设每种排列等可能，那么待插入元素平均会跨过当前已排序部分的大约一半。常数因子减小了，但求和仍是二次量级，所以平均时间仍为 $\Theta(n^2)$。如果真实输入常常接近有序，这个均匀分布就不合适，平均结论也会变化。

还要区分“平均运行时间”和“期望运行时间”。前者的随机性来自输入分布；后者常用来描述算法自己抛硬币、抽样或随机打乱所产生的随机性。即使外部输入固定，随机算法的执行路径也会变化，此时对算法内部的随机选择取期望。

为什么只保留主导项

从 $an^2+bn+c$ 变为 $\Theta(n^2)$，删掉了低阶项和首项常数。这不是说常数不影响现实速度，而是说当 $n$ 足够大时，$n^2$ 相对 的优势会无限扩大，固定常数无法改变最终的增长关系。

例如，一个实现精细的三次算法可能在小输入上快于一个常数很大的二次算法。但只要输入继续增大，三次项最终会超过二次项。渐近结论告诉我们最终趋势，不负责给出具体交叉点；交叉点要结合实现和基准测试判断。

用大 O、大 Ω 与大 Θ表达边界

渐近记号描述的是函数集合。为避免符号被负值干扰，下面默认 $f(n)$ 和 $g(n)$ 在足够大的 $n$ 上都非负。定义中的“足够大”由阈值 $n_0$ 表示：我们允许小规模部分表现得杂乱，只要求从某处开始始终满足关系。

大 Θ：上下同时夹住

如果存在正常数 $c_1$、$c_2$ 和 $n_0$，使所有 $n\ge n_0$ 都满足：

那么 $f(n)\in\Theta(g(n))$。完整地说：

$g(n)$ 此时是 $f(n)$ 的渐近紧确界。所谓“紧确”，就是 $f$ 既不会比 $g$ 低一个增长层级，也不会比 $g$ 高一个增长层级；两者最终只差常数倍。

大 O：只给上界

如果存在正常数 $c$ 和 $n_0$，使所有 $n\ge n_0$ 都满足：

那么 $f(n)\in O(g(n))$。大 O 只承诺“不超过某个常数倍”，不承诺这个界最紧。于是：

这个说法完全正确，只是比较宽松。若要准确表达线性函数的增长阶，应该写 $n\in\Theta(n)$。

大 Ω：只给下界

如果存在正常数 $c$ 和 $n_0$，使所有 $n\ge n_0$ 都满足：

那么 $f(n)\in\Omega(g(n))$。它表示 $f$ 最终至少增长得和 $g$ 一样快。

把记号用于“算法运行时间”时，还要看语句覆盖了哪些输入。若说某算法的最坏运行时间属于 $O(g(n))$，那么任意规模为 $n$ 的输入都受这个上界约束。若不加情形限定，直接说算法运行时间属于 $\Omega(g(n))$，通常表示每一个足够大的输入都至少需要常数倍的 $g(n)$ 时间，也就是对最好情形给出下界。

这与“最坏运行时间属于 $\Omega(g(n))$”不同。后一句只要存在能让算法耗费这么多时间的输入即可，并不能推出所有输入都这么慢。例如插入排序的最坏时间属于 $\Omega(n^2)$，但有序输入只需要线性时间，所以算法对所有输入的统一下界不能写成 $\Omega(n^2)$。

三个记号的关系可以压成一句话：

用定义证明，而不是只看最高次项

以 $f(n)=\frac{1}{2}n^2-3n$ 为例。我们要找正常数 $c_1,c_2,n_0$，让它在 之后被两个 的常数倍夹住。两边除以 ：

取 $c_1=\frac{1}{14}$、$c_2=\frac{1}{2}$、 就能满足定义。常数并不唯一；证明只需要找到一组可行值。

反过来，$6n^3$ 不属于 $O(n^2)$。假设存在固定常数 $c$ 使 $6n^3\le cn^2$，约掉 后得到 。左边随 无界增长，不可能永远小于固定的 。

对任意首项系数为正的 $d$ 次多项式：

都有 $p(n)\in\Theta(n^d)$。这里的“看最高次项”是形式定义的快捷结论，不是替代定义的口号。

等号其实是集合成员关系

算法文章常写 $f(n)=O(g(n))$，但严格含义是 $f(n)\in O(g(n))$。这种等号不能像普通等式一样随意反向。例如 $n=O(n^2)$ 成立，却不能推出 。

当渐近记号出现在更长的式子中，它代表某个未命名的函数。例如：

右侧的 $\Theta(n)$ 代表这里恰好可以取 $3n+1$。这种写法会隐藏无关细节，但使用时要记住它不是一个可以随意约分的普通数值。

小 o 与小 ω描述严格差距

大 O 和大 Ω允许边界是紧的，也允许不紧。若我们想明确说“增长速度严格更低”或“严格更高”，就要使用小 o 和小 ω。

小 o：比任何固定倍数都小

若对每一个正常数 $c$，都能找到阈值 $n_0$，使所有 $n\ge n_0$ 满足：

那么 $f(n)\in o(g(n))$。注意量词顺序：不是找“某一个”够大的 $c$，而是无论给多小的正数 $c$，$f$ 最终都能落到 $cg$ 下方。

当极限存在时，可以用比值理解：

因此 $2n\in o(n^2)$，因为 $2n/n^2=2/n\to0$；但 $2n^2$，因为比值恒为 ，没有趋近于 。

小 ω：比任何固定倍数都大

若对每一个正常数 $c$，都能找到阈值 $n_0$，使所有 $n\ge n_0$ 满足：

那么 $f(n)\in\omega(g(n))$。当极限存在时：

例如 $n^2/2\in\omega(n)$，但 $n^2/2\notin\omega(n^2)$。后者仍然只差常数倍，属于 。

五种记号放在一起

一个常见误区是把 $O$ 当成“小于”，把 $\Theta$ 当成“等于”。更准确的类比是：$O$ 像“$\le$”，$\Omega$ 像“$\ge$”，$\Theta$ 像“同阶相等”，$o$ 像严格的“”， 像严格的“”。类比只帮助记忆，正式证明仍以常数和阈值的定义为准。

比较增长函数时有哪些规则

把渐近记号当成一种关系后，许多代数式比较可以快速传递，但并非所有实数比较规则都能照搬。

传递、自反与对称

对于最终为正的函数，五种记号都具有传递性。例如：

$\Theta$、$O$、$\Omega$ 具有自反性：每个函数都与自己同阶，也当然是自己的上界和下界。小 $o$ 与小 $\omega$ 没有自反性，因为函数不可能严格慢于或严格快于自身。

$\Theta$ 具有对称性：

上界与下界可以转置：

严格关系也一样：

并非任意两个函数都能比较

实数 $a$ 与 $b$ 总能判断 $a<b$、$a=b$ 或 $a>b$。函数的渐近关系没有这种三分性。考虑：

在偶数点，$f/g=1/n\to0$；在奇数点，$f/g=n\to\infty$。因此 $f$ 既不属于 $O(g)$，也不属于 。它在两种增长状态间反复跳动，没有最终稳定在某一侧。

加法、乘法与对数的常用化简

对最终非负的函数，顺序执行两段代码时，总时间是两者相加，而和通常由较大的增长项主导：

例如 $\Theta(n)+\Theta(n^2)=\Theta(n^2)$。嵌套工作常导致乘法，例如外层 $n$ 次、内层每次 $m$ 次，得到 。但只有当内层次数确实每轮都是同一量级时才能直接相乘；三角形循环要先写求和。

固定底数的对数只差常数倍。由换底公式：

只要 $b,c>1$ 且为常数，就有 $\log_b n\in\Theta(\log_c n)$。因此复杂度里常把底数省略；需要计算精确轮数时，底数仍然有意义。

常见函数的增长谱系

复杂度比较经常落到几类固定函数上。先记住主干关系，再用极限或定义处理接近的情况，会比背一长串孤立结论可靠。

单调性、取整与模运算

若 $m\le n$ 能推出 $f(m)\le f(n)$，则 $f$ 单调不减；若严格小于能推出函数值也严格小于，则是严格递增。单调性常用于把离散输入夹在连续函数之间。

向下取整 $\lfloor x\rfloor$ 是不大于 $x$ 的最大整数，向上取整 $\lceil x\rceil$ 是不小于 $x$ 的最小整数：

取整最多引入一个常数误差，通常不改变趋向无穷时的增长阶。例如 $\lfloor n/2\rfloor\in\Theta(n)$，并且：

模运算把整数映射到有限余数。对正整数 $m$：

$a\equiv b\pmod m$ 表示两者除以 $m$ 的余数相同，等价于 $m$ 整除 $b-a$。它本身不是增长函数，却经常出现在哈希、循环下标和周期结构中。

对数、多项式与指数

对于任意固定的 $k>0$、$a>0$ 和 $c>1$：

以及：

也就是说，任何固定次幂的对数最终都慢于任何正次数多项式；任何固定次数多项式最终都慢于底数大于 $1$ 的指数函数。即使指数底数只是 $1.01$，它最终也会超过 $n^{100}$，只是交叉点可能非常大。

“多项式时间”指被某个固定次数 $n^k$ 上界控制；“多对数时间”指被某个固定次数 $(\log n)^k$ 上界控制。这里的次数必须是与输入无关的常数。

阶乘、斐波那契与 $n^n$

阶乘为：

它比任意固定底数的指数 $c^n$ 增长得快，又比 $n^n$ 慢：

一个更精细的近似是：

由此可得：

斐波那契数满足 $F_0=0$、$F_1=1$、$F_i=F_{i-1}+F_{i-2}$。它的值按黄金比例 的幂增长，因此 。这说明“递推定义看起来只做加法”并不代表函数值增长缓慢。

迭代对数几乎不动

函数迭代 $f^{(i)}(n)$ 表示从 $n$ 开始连续应用 $f$ 共 $i$ 次。迭代对数 $\log^* n$ 是把对数连续应用多少次后，结果才不大于 ：

它增长极慢。以二为底，$\log^*2=1$、$\log^*4=2$、$\log^*16=3$、。不要把 与 混淆：前者是重复取对数，后者是取对数后做 次幂。

一条实用的增长顺序

对固定正常数 $a,k$ 和固定 $c>1$，常见顺序可以写成：

符号 $\prec$ 在这里表示左侧严格渐近慢于右侧。若 $k=1$，$\log n$ 与 $(\log n)^k$ 是同一个量级；写这条谱系时默认比较的是能产生严格差异的参数取值。

从循环结构算出复杂度

看到循环时，先写“每轮做多少次”，再求和。只有循环范围彼此独立时，才能直接把层数变成乘法。

固定次数与线性扫描

下面两段分别执行固定次数与随数组长度增长的次数：

function first(items) {
  return items[0];
}
 
function contains(items, target) {
  for (const item of items) {
    if (item === target) return true;
  }
  return false;
}

数组按下标访问是 $\Theta(1)$。线性查找最好情形只比较一次，是 $\Theta(1)$；最坏情形要检查所有 $n$ 个元素，是 $\Theta(n)$。若目标等可能位于每个位置且一定存在，平均检查次数是 $(n+1)/2$，仍为 。

每次缩小固定比例

若循环每次把待处理规模减半，执行次数 $k$ 满足：

于是 $k\ge\log_2 n$，复杂度为 $\Theta(\log n)$。二分查找、堆向上调整、某些树操作都出现这种结构。关键不是代码里有没有除法，而是剩余问题规模是否按固定比例收缩。

三角形循环要用算术级数

let count = 0;
for (let i = 1; i <= n; i += 1) {
  for (let j = 1; j <= i; j += 1) {
    count += 1;
  }
}

内层不是每轮都执行 $n$ 次，而是依次执行 $1,2,\ldots,n$ 次。总次数为：

结果仍是平方，但推导过程比“看到双层循环就是平方”可靠。若内层只执行到 $\sqrt{i}$，或每次把 $j$ 翻倍，答案就会变化。

四类常用求和

循环分析里最常见的是下面几类式子。

线性性质允许拆分常数和各项：

算术级数解释逐轮增加的工作：

若每轮代价本身是平方或立方，也有：

几何级数解释按固定倍数扩张或缩小的层级。对 $x\ne1$：

当 $|x|<1$ 时，无穷递减几何级数收敛到：

调和级数常出现在“第 $i$ 个对象以 $1/i$ 的概率触发操作”或分组分析中：

望远镜求和把中间项相互抵消。例如：

乘积也可以通过取对数转为求和。对正数序列 $a_k$：

这个技巧常用于比较递归树叶子数、组合数量和阶乘的增长。这些公式的目的不是增加数学负担，而是把“不规则的每轮次数”变成可比较的增长函数。

递归先写关系式

递归算法不能只数函数体有几行。若规模为 $n$ 的问题分成两个规模为 $n/2$ 的子问题，并在线性时间内合并，运行时间满足：

递归树每层合计做 $\Theta(n)$ 工作，共有 $\Theta(\log n)$ 层，所以总时间是 $\Theta(n\log n)$。如果同样的两个子问题大量重叠却没有缓存，递归调用数可能呈指数增长。先写递推关系，才能看清分支数、子问题规模和每层额外工作各自贡献了什么。

把复杂度结论用于真实决策

复杂度的价值不在于给代码贴标签，而在于帮助我们排除无法扩展的方案，并明确还缺哪些证据。

先写清楚结论的四个限定

一条完整的复杂度结论至少应让读者知道：

1. 输入规模是什么，例如元素数 $n$，还是顶点数 $V$ 与边数 $E$。
2. 统计什么资源，例如最坏运行时间、平均比较次数或额外空间。
3. 使用什么计算模型，例如机器字操作是否按常数时间计。
4. 渐近界是否紧确。能证明 $\Theta$ 时不要只留下宽松的 $O$。

例如，“对含 $V$ 个顶点、$E$ 条边的邻接表，算法访问每个顶点和每条边常数次，因此最坏运行时间是 $\Theta(V+E)$，额外空间是 $\Theta(V)$”就比“复杂度是线性的”清楚得多。

把预处理也算进去

如果只查一次，在无序数组上做线性查找的总成本是 $\Theta(n)$。若先排序再二分，预处理通常要 $\Theta(n\log n)$，单次查询是 $\Theta(\log n)$。查询次数为 $q$ 时，两种方案可分别写成：

当 $q$ 很小时，预处理未必划算；当同一批数据被反复查询时，索引或排序成本可以被摊薄。这里不能只比较一次查询的 $n$ 与 $\log n$，还要把建立结构、更新结构和额外内存算进总账。

保证、分布与随机性要分开

最坏情形适合延迟上限、实时约束和对抗性输入，因为它不依赖输入分布。平均情形可以更贴近常见负载，但前提是分布假设有依据，并且需要在数据变化后重新核对。随机算法的期望时间则来自算法内部随机性；它能减少对某种固定输入排列的依赖，却仍可能需要单独分析尾部风险或最坏上限。

渐近分析与基准测试互相补位

渐近分析先排除增长阶明显不合适的候选，并解释输入扩大后的趋势。基准测试再回答常数因子、缓存局部性、编译器优化、分配开销和具体交叉点。两者不能互相替代：只做基准测试容易被小样本误导；只写大 O 则无法预测当前业务规模下的实际延迟。

一个实用流程是：