大O记号（big-O notation）
/ big oh /
假设你想说某个东西有多大，却不想钉死它的精确值——就像说人群「数以千计」，而不去一个一个数人头。大O记号正是给函数用的这种诚实的上界。当我们写 f(x) = O(g(x)) 时，是在断言：在我们关心的那个极限下（x 趋于无穷，或 x 趋于零），f 的增长永远不会快过 g，至多差一个固定的常数倍。
精确的含义是：当 x 趋于某极限时 f(x) = O(g(x))，意思是存在一个常数 C 以及该极限附近的一个邻域，在其中 f(x) 的绝对值始终小于 C 乘以 g(x) 的绝对值。所以 O(g) 就是所有最终被 g 的某个常数倍所压住的函数构成的集合。例如，当 x 趋于无穷时 3x^2 + 5x = O(x^2)，因为 x 大时是 x^2 项定下尺度，取常数 C = 4 就绰绰有余。在 x = 0 附近，同样的记号要反过来读：sin x - x = O(x^3) 表示减去 x 之后剩下的部分，在 x 很小时不会大过 x^3 的一个常数倍。
这是一切渐近分析的基本语法，处处可见：泰勒展开的误差项（f(x) = f(0) + f'(0) x + O(x^2)）、算法的代价（排序为 O(n log n)）、以及渐近级数的余项。一个诚实的提醒是：大O完全隐藏了常数。O(x^2) 告诉你增长的形状，却不告诉你那个常数是 0.001 还是 10^9，所以两个同为 O(n^2) 的方法在实践中可能天差地别。
当 x 趋于 0 时 e^x = 1 + x + x^2/2 + O(x^3)；当 x 趋于无穷时 x^2 + 100x = O(x^2)。
同一个符号 O 既能描述在 0 附近的微小余项，也能描述在无穷处的增长率——所取的极限必须每次都讲清楚。
f = O(g) 是单向的断言，而非真正的等式：不能把 O 「消去」，也不能反过来写成 g = O(f)。它只用 g 给 f 一个上界，仅此而已。