大 O 表示法

学习目标

本节学习大 O 表示法。

大 O 表示法用于描述算法成本增长的上界趋势。它不追求精确计算每一步耗时，而是用简洁方式表达：当输入规模变大时，成本大概按什么级别增长。

假设两个算法的操作次数分别是：

T_1(n) = 2n

T_2(n) = 10n

从具体操作次数看，第二个算法大约是第一个的 5 倍。但它们的增长趋势相同：输入规模翻倍时，操作次数也大约翻倍。

因此，在大 O 表示法中，它们都记为 $O(n)$ 。

这并不是说常数不重要，而是说复杂度分析首先关注增长级别。常数差异可以在实际性能优化时再考虑。

再看一个例子：

T(n) = n^2 + 100n + 1000

当 $n$ 很小时， $100n$ 和 $1000$ 可能影响明显。但当 $n$ 变得很大时， $n^2$ 的增长速度会超过其他项，成为主导因素。

所以这个函数的大 O 复杂度通常记为：

O(n^2)

这里的核心思想是：保留增长最快的主导项，忽略低阶项和常数系数。

分析大 O 时，可以使用几个常见简化规则：

例如，一个函数先遍历一次数组，再执行两层嵌套循环。它的操作增长可以粗略表示为：

T(n) = n + n^2

最终保留主导项，记为 $O(n^2)$ 。

很多教材会把大 O 解释为上界。对于初学者来说，可以先把它理解为“当规模变大时，成本增长不会超过某个主要级别”。

例如，顺序查找在最坏情况下需要检查所有元素，所以通常说它的最坏时间复杂度是 $O(n)$ 。

不过在学习阶段，不要陷入过度形式化的数学证明。先能够用大 O 表达常见代码的增长趋势，更重要。

$O(1)$ 不一定永远比 $O(n)$ 快。

如果 $n$ 很小，一个 $O(n)$ 的简单循环可能比一个常数开销很大的 $O(1)$ 操作更快。大 O 描述的是增长趋势，不是某一次运行的绝对耗时。

但是，当输入规模持续变大时，复杂度级别通常会越来越重要。一个 $O(n^2)$ 的算法可能在 100 个数据上还能接受，但在 100 万个数据上往往无法承受。

大 O 表示法用来描述算法成本随输入规模增长的主要趋势。

使用大 O 时，通常忽略常数系数和低阶项，只保留增长最快的主导部分。它不是精确运行时间，也不是绝对速度判断，而是比较算法可扩展性的重要工具。