大 O 表示法——轻松理解时间复杂度

大 O 表示法告诉你：当输入规模变大时，算法的运行时间或内存使用量会如何增长。如果你想问“问题变得大很多之后会怎样？”，大 O 就是回答这个问题的标准方式。

这就是为什么人们会说线性搜索是 $O(n)$，二分搜索是 $O(\log n)$。它的目标不是预测某台机器上精确的毫秒数，而是比较增长模式。

大 O 表示什么

如果一个算法在输入规模为 $n$ 时所需时间是 $T(n)$，那么

$$T(n) = O(f(n))$$

表示存在常数 $C > 0$ 和 $n_0$，使得

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

这说明：对于足够大的输入，大 O 给出的是关于增长速度的一个上界。

用更直白的话说：当 $n$ 足够大以后，运行时间的增长不会超过 $f(n)$ 的某个常数倍。

为什么大 O 很有用

大 O 提供了一种不依赖具体机器的算法比较方式。一个程序在某台笔记本上可能比另一台跑得更快，但增长趋势依然重要。

当输入规模变化很大时，这种趋势尤其关键。一个对 $100$ 个元素还算可行的算法，如果增长率很差，到了 $10^6$ 个元素时就可能完全不实用了。

常见时间复杂度一览

• $O(1)$：随着 $n$ 增大，工作量仍然保持有界。
• $O(\log n)$：工作量增长很慢，常见于问题规模被反复缩小的情况。
• $O(n)$：工作量大致与输入规模成正比。
• $O(n \log n)$：比线性稍大一些，常见于高效排序算法。
• $O(n^2)$：工作量像输入规模的平方那样增长，通常来自对同一批数据进行嵌套循环。

这些标签比较的是增长速度，不是精确速度。对于较小输入，如果常数因子很大，$O(n)$ 算法仍然可能比 $O(n^2)$ 算法更慢。

示例：为什么线性搜索是 $O(n)$

假设你从左到右扫描一个列表，寻找某个目标值。在最坏情况下，目标不存在，或者恰好在最后一个位置，因此你可能需要把每个元素都检查一遍。

如果列表有 $n$ 个元素，那么检查次数最多就是 $n$。所以它的最坏情况时间复杂度是

$$O(n)$$

这里最值得记住的一点很简单：如果列表大小翻倍，最坏情况下的检查次数也大致会翻倍。这正是大 O 想要刻画的模式。

大 O 忽略了什么

在比较大规模输入下的增长时，大 O 会有意忽略常数因子和低阶项。

例如，如果

$$T(n) = 3n + 2$$

那么 $T(n)$ 仍然是 $O(n)$。常数 $3$ 和额外的 $2$ 会影响精确计时，但不会改变主要的增长模式。

这并不意味着常数在实际中永远不重要。它只是说明，大 O 回答的是一个更具体的问题：当 $n$ 变得很大时，代价会如何缩放。

常见的大 O 误区

误区 1：把大 O 当成精确运行时间

$O(n)$ 并不表示运行时间恰好是 $n$ 步。它表示当 $n$ 足够大时，增长速度被 $n$ 的某个常数倍所上界。

误区 2：忘记“大 $n$”这个条件

形式化定义只要求对所有 $n \ge n_0$ 成立。大 O 讨论的是渐近行为，而不是每一个很小的输入。

误区 3：以为大 O 总表示典型运行时间

在算法讨论中，大 O 常常描述最坏情况时间复杂度，但这只是与具体语境相关的惯例。平均情况和最好情况复杂度是不同的问题，应该明确标注。

误区 4：只用大 O 比较算法

大 O 很重要，但在真实系统中，内存使用、实现成本和常数因子也可能同样重要。

你会在哪些地方看到大 O 表示法

大 O 常见于计算机科学、离散数学和性能分析中。它在比较搜索、排序、图遍历和动态规划算法时尤其有用。

更广泛地说，只要你关心的是一个过程如何随规模变化，而不只是它在某个固定规模下的表现，就会用到它。

试试一个类似的例子

考虑一个简单的嵌套循环，它遍历一个 $n \times n$ 的网格。数一数内层操作一共执行了多少次。如果总工作量像 $n^2$ 那样增长，你就得到了一个很具体的例子，说明为什么对同一批数据进行重复循环时，常常会出现 $O(n^2)$ 的行为。