部分摘抄自《计算理论导引 第3版》

本质

因为算法的精确运行时间通常为一个复杂的表达式，所以一般只是估计它的趋势和级别，通过一种被称作渐进分析（asymptotic analysis）的方便的估计形式，可以试图了解算法在长输入上的运行时间。为此，只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其他低次项——因为在长输入上，最高次项的影响相比其他项占据主导地位。

例如，函数
$$
f(n) = 6 n^3 + 2n^2 +20n + 45
$$
有四项，其中最高次项为$6n^3$，忽略系数6，称$f$渐进地不大于$n^3$，表达这种关系的渐进记法（asymptotic notation）或大O记法（big-O notation）是$f(n) = O(n^3)$。

当$f(n) = O(g(n))$时，称作$g(n)$为$f(n)$的上界（upper bound），或者更准确地说，是渐进上界（asymptotic upper bound）以强调忽略了系数。

数学定义

设$f$和$g$为两个函数，$f，g:\mathbf{N} \rightarrow \mathbf{R}^+$。称$f(n)=O(g(n))$，当且仅当$\exists c, n_0$使得$\forall n \geq n_0$，有
$$
f(n) \leq cg(n)
$$

根据定义，其实 $f(n) = O(n^4)$ 同样成立，所以它也是$f$的一个渐进上界。

我的理解

实际应用中，表达时间复杂性时，忽略最高项系数是因为我们对于时间复杂性的关注点主要在项级，因为当面对一个长度超长输出甚至长度近似于 $+\infty$ 时，有
$$
\lim_{n \rightarrow + \infty}\frac{an^3}{bn^2} = +\infty，其中a,b \neq 0
$$
可以看到项级对复杂度的影响远大于系数，因此我们会在表达时忽略系数。

另外，大O计法由于忽略系数，其对于$\log$的表达也是特殊的，例如根据先前的知识，$f(n) = \log_2 n$函数的大O记法应为：
$$
f(n)= c \log_{2}n=O(log_{2}n)
$$

但是恒有等式
$$
\log_{b}n = \frac{\log_{2}n}{\log_{2}b}
$$
那么
$$
c\log_{2}n = c\log_{2}b \cdot log_{b}n
$$
其中在当前语境下，$c\log_{2}b$为一个与$n$无关的系数，因此省略，而$b$可以为任意值，因此同样省略。

最终，包含$\log$的大O记法就表示为
$$
f(n) = O(\log{n})
$$

在算术表达式中的计算

$$
f(n) = O(n^3) + O(n)
$$

此时符号O的每次出现都可视作有一个被隐藏了的系数，因此此等式被转换为了
$$
f(n) = an^3 + bn = O(n^3)
$$
由于$O(n^3)$的影响占据主导地位，因此$O(n)$最终被省略了。

小o记法

小o记法：一个函数渐进地小于另一个函数。但是实际上我们常用的为大O记法，它相比于小o记法多了一个等于的情况。

为何大O记法在实践中更加常用

正如前文所说，大O记法比小o记法更为宽松，在情况$f(n) = O(n)$时，算法具体的时间复杂度可能为$3n$、$n + \log n$甚至性能更优的$0.5n$。他们的性能都处于“同一个级别”，但是当采用小o记法时，存在$f(n) = 3n \neq o(n)$的情况，在进行算法分析时往往过于严格：算法往往关注“最坏情况的上界”，并非“严格更优”。

总结

大O记法因其宽松性、实用性和广泛接受度成为算法分析的主流工具，而小o的严格性使其更多用于理论数学或特定渐进分析场景。两者的选择本质上是需求驱动的：工程上需要简洁的上界描述，而数学上需要精确的渐进关系。因此，大O自然成为实践中更常见的选择。（deepseek）