大 O 记号

大 O 记号是数学中的一种记号，用于表示：当自变量趋近某个指定的极限时，一个函数的绝对值不超过另一个函数的常数倍。在计算机科学中，它通常用来描述算法的运行时间或内存需求如何随输入规模增大而增长。它表示的是渐近上界，不一定是确切的增长速率，并且忽略常数因子以及相关极限区域之外的行为。(xlinux.nist.gov)

形式定义

设函数 $f$ 和 $g$ 在充分大的正整数上有定义，且当 $n$ 充分大时， $g(n)>0$ 。表达式

f(n)=O(g(n))\qquad(n\to\infty)

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

|f(n)|\le Cg(n) \quad\text{对所有 }n\ge n_0\text{ 均成立。}

这些常数不能依赖于 $n$ 。对于取值非负的资源计数函数，可以省略绝对值符号。由于设有阈值，即使这一不等式对有限多个较小的输入不成立，也不影响该上界的有效性。(xlinux.nist.gov)

更一般地，在数学分析中， $x\to a$ 时的 $f(x)=O(g(x))$ 表示：在相关极限附近，凡是比值有定义的地方， $|f(x)/g(x)|$ 都保持有界。自变量可以趋于无穷大、零或其他点，不一定代表输入规模。(dlmf.nist.gov)

严格来说， $O(g)$ 表示满足该上界条件的一组函数，因此写成 $f\in O(g)$ 能更明确地表达其含义。惯用写法 $f=O(g)$ 中的等号并不表示通常意义上具有对称性的相等关系：不能将这个表达式反过来，推断出 $g=O(f)$ 。(ocw.mit.edu)

示例与运算规则

考虑多项式

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

当 $n\ge1$ 时， $f(n)\le15n^2$ ，因此 $f(n)=O(n^2)$ 。它也属于 $O(n^3)$ ，这说明一个有效的上界未必是最能准确反映增长情况的上界。常数因子和低次项不会改变多项式的主要增长阶。(xlinux.nist.gov)

当用于比较的函数在自变量充分大时非负，上述定义可导出以下实用规则：

若 $f=O(g)$ 且 $h=O(k)$ ，则 $f+h=O(g+k)$ 。
在相同假设下， $fh=O(gk)$ 。
若 $f=O(g)$ 且 $g=O(h)$ ，则 $f=O(h)$ 。
乘以一个固定的非零常数，不会改变函数所属的大 O 类。(cs.yale.edu)

这些规则必须应用于实际的操作次数。嵌套循环并不必然意味着平方时间复杂度：循环的迭代次数和循环体的执行成本共同决定了总工作量。(introcs.cs.princeton.edu)

算法分析与增长类别

在计算复杂性中，大 O 记号用于描述在指定的输入规模度量和计算模型下，资源使用量的增长情况。时间复杂度衡量操作次数，而空间复杂度衡量存储需求。因此，同一种数据结构或算法的时间上界与空间上界可能不同。(xlinux.nist.gov)

假设基本操作的成本为常数，常见的上界如下：

上界	通常描述	示例
$O(1)$	常数阶	通过下标访问数组元素
$O(\log n)$	对数阶	在有序数组中进行[[binary-search
$O(n)$	线性阶	扫描所有元素
$O(n\log n)$	线性对数阶	[[merge-sort
$O(n^2)$	平方阶	检查每一对元素
$O(2^n)$	指数阶	枚举 $n$ 个元素的所有子集

只要对数的底是大于一的固定值，改变底数就只会引入一个常数因子，因此不会改变这些大 O 类。(cs.princeton.edu)

使用递归的算法通常会产生递推关系。例如，归并排序的分治法结构产生的递推关系包含两个规模减半的子问题，以及线性成本的合并工作，由此得到 $O(n\log n)$ 的时间上界。(introcs.cs.princeton.edu)

大 O 本身并不意味着“最坏情况”。只要明确所约束的函数，上界就可以描述最坏情况、最好情况或平均情况下的成本。关于平均情况的结论需要对输入作出假设；而随机化算法的期望上界则可以通过对算法内部的随机选择取平均来得到。(algs4.cs.princeton.edu)

近似误差与解释上的局限

在渐近展开中，大 O 可以用来表示余项的大小。例如，

e^x=1+x+O(x^2)\qquad(x\to0)

表示在充分接近零的地方，差值 $e^x-1-x$ 的绝对值不超过 $x^2$ 的某个常数倍。与自变量趋于无穷大时的运行时间上界不同，这里描述的是趋于零的误差。(dlmf.nist.gov)

渐近运行时间上界并不直接给出以秒为单位的执行时间。常数因子、实现细节和机器特性都会影响实际性能；渐近上界更小，也不意味着对每一种有限的输入规模都执行得更快。输入的表示方式同样重要：存储的数据项数量与编码这些数据项所需的比特数，是两种不同的规模度量。(introcs.cs.princeton.edu)

形式定义

示例与运算规则

算法分析与增长类别

相关渐近记号

近似误差与解释上的局限