计算机考研之数据结构：大 O 记号

《数据结构》不仅是计算机考研 408 的必考科目，也是很多自命题学校要考的科目。这里将刊登系列文章，对《数据结构》这门课的某些问题进行讲解，供学习者参考。

在计算机科学领域，算法的效率至关重要。随着数据规模的不断增大，一个高效的算法能够显著提升系统性能，而低效的算法则可能导致程序运行缓慢甚至无法正常工作。为了准确评估算法的效率，我们需要一种科学的方法来衡量算法随着输入规模增长时的运行时间或空间使用情况。大 O 记号（Big O Notation）就是这样一种广泛应用于算法分析的工具，它为我们提供了一种简洁而有效的方式来描述算法的时间复杂度和空间复杂度。

不过，大 O 记号并非唯一用于算法复杂度分析的工具，与之相关的还有大 Ω 记号、大 Θ 记号等，它们从不同角度完善了对算法复杂度的刻画。本文仅介绍大 O 记号，其他的分析工具，后续讲解。

大 O 记号的定义

大 O 记号的定义较为严谨，但理解起来并不困难。

假设存在正常数 $c$ 和 $n_0$ ，当输入规模 $n$ 大于等于 $n_0$ 时，算法的运行时间函数 $T(n)$ 始终小于等于 $c$ 乘以另一个函数 $f(n)$ ，即：
$$T(n)\le cf(n)$$
那么我们就可以记为：
$$T(n)=O(f(n))$$

为了更直观地理解，来看一个例子。

假设有两个函数，$T(n)=1000n$ 和 $f(n)=n^2$ 。从下图中可以清晰地看到，当 $n$ 的值小于 1000 时，$1000n$ 的值大于 $n^2$ ；然而，当 $n$ 大于 1000 后，情况发生了反转，$1000n$ 小于 $n^2$ 。

根据大 O 记号的定义，因为当 $n$ 足够大（这里是大于 1000）时，$T(n)$ 始终小于等于某个常数（这里可以取 $c=1$）乘以 $f(n)$ ，所以可以得出 $T(n)=O(f(n))$，即 $T(n)=O(n^2)$ 。这意味着，随着 $n$ 的不断增大，$T(n)$ 的增长速度不会超过 $n^2$ 的增长速度， $n^2$ 是 $T(n)$ 的一个上界。

大 O 记号的性质

性质 1：常系数可忽略

对于任意常数 $c>0$ ，有 $O(f(n))=O(c\cdot f(n))$ 。

证明：

如果 $T(n)=O(f(n))$ ，那么根据大 O 记号的定义，存在正常数 $c_1$ 和 $n_1$ ，使得当 $n\ge n_1$ 时， $T(n)\le c_{1}f(n)$ 。

现在考虑 $c\cdot f(n)$ 。令 $c_2=\frac{c_1}{c}$ （因为 $c>0$ ， $c_2$ 是有定义的）。当 $n\ge n_1$ 时，我们有 $T(n)\le c_{1}f(n)=c\cdot c_{2}f(n)$ 。

所以 $T(n)=O(c\cdot f(n))$ 。

反之，如果 $T(n)=O(c\cdot f(n))$ ，存在正常数 $c_3$ 和 $n_2$ ，使得当 $n\ge n_2$ 时， $T(n)\le c_3(c\cdot f(n))=(c_{3}c)f(n)$ 。令 $c_4=c_{3}c$ ，则 $T(n)=O(f(n))$ 。

例如，对于函数 $f(n)=n^2$ 和 $g(n)=2n^2$ ，尽管它们的系数不同，但从增长趋势的角度来看，它们是相同的。当 $n$ 持续增大时， $2n^2$ 与 $n^2$ 增长速度的差异仅仅是一个常数倍（此处为 2 倍）。这样的常数倍差异在大 O 记号中被忽略不计，所以 $O(2n^2)=O(n^2)$ 。

可以通过另一个例子进一步加深理解。假设有函数 $f(n)=2n^3+3n^2+2n+1$ 和 $g(n)=n^3$ 。如下图所示，随着 $n$ 增大， $f(n)$ 和 $g(n)$ 的图像趋势相似。

通过求极限的方法，计算当 $ n $ 趋近于无穷大时两个函数的比值： ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}={\lim }_{n\to \infty }\frac{2n^3+3n^2+2n+1}{n^3}={\lim }_{n\to \infty }(2+\frac{3}{n}+\frac{2}{n^2}+\frac{1}{n^3})=2$

这个结果表明 $f(n)$ 和 $n^3$ 是同阶的。如果 $T(n)=O(f(n))$ ，那么根据大 O 记号的性质， $T(n)=O(f(n))=O(n^3)$ 。

性质 2：低次项可忽略

对于任意常数 $a>b>0$ ，有 $O(n^a+n^b)=O(n^a)$ 。

证明：

我们知道 ${\lim }_{n\to \infty }\frac{n^a+n^b}{n^a}={\lim }_{n\to \infty }(1+n^{b-a})$ 。因为 $a>b>0$ ，所以 $b-a<0$ 。当 $n\to \infty$ 时， ${\lim }_{n\to \infty }{n}^{b-a}=0$ 。所以 ${\lim }_{n\to \infty }\frac{n^a+n^b}{n^a}=1$ 。

这意味着存在正常数 $c=2$ （例如）和 $n_0$ （我们可以找到一个合适的 $n_0$ ，使得当 $n\ge n_0$ 时， $n^a+n^b\le 2n^a$ ）。根据大 O 记号的定义， $O(n^a+n^b)=O(n^a)$ 。

例如，对于函数 $h(n)=n^3+n^2$ ，随着 $n$ 持续增大， $n^3$ 的增长速度比 $n^2$ 快得多。 $n^2$ 对函数整体增长趋势的影响越来越小。所以 $O(n^3+n^2)=O(n^3)$ 。

大 O 记号的相关定理

定理 1：多项式函数的大 O 表示

若 $f(n)=a_m{n}^m+a_{m-1}{n}^{m-1}+\cdots +a_2{n}^2+a_{1}n+a_0$ 是一个 $m$ 次多项式，则 $T(n)=O(n^m)$ 。

证明：如果 $f(n)=a_m{n}^m+a_{m-1}{n}^{m-1}+\cdots +a_2{n}^2+a_{1}n+a_0$ 是一个 $m$ 次多项式。

我们知道 ${\lim }_{n\to \infty }\frac{f(n)}{n^m}={\lim }_{n\to \infty }(a_m+\frac{a_{m-1}}{n}+\cdots +\frac{a_2}{n^{m-2}}+\frac{a_1}{n^{m-1}}+\frac{a_0}{n^m})$ 。

当 $n\to \infty$ 时， $\frac{a_{m-1}}{n},\cdots ,\frac{a_0}{n^m}$ 都趋近于 0。所以 ${\lim }_{n\to \infty }\frac{f(n)}{n^m}=a_m\ne 0$ 。

存在正常数 $c=|a_m|+1$ （如果 $a_m\ne 0$ ）和 $n_0$ ，使得当 $n\ge n_0$ 时， $|f(n)|\le c|n^m|$ 。根据大 O 记号的定义， $T(n)=O(n^m)$ 。

这一定理是基于前面提到的性质 1 和性质 2 得出的。因为在多项式中，最高次项 $a_m{n}^m$ 的增长速度在 $n$ 足够大时，远远超过其他低次项，并且根据性质 1，系数 $a_m$ 可以忽略，所以整个多项式函数的大 O 表示就是 $O(n^m)$ 。例如，对于多项式函数 $f(n)=5n^4+3n^3+2n^2+n+1$ ，其大 O 表示为 $O(n^4)$ 。

定理 2：求和与求积定理

设 $T_1(n)=O(f(n)),T_2(n)=O(g(n))$ ，则有：

• 求和定理： T 1 ( n ) + T 2 ( n ) = max ⁡ { O ( f ( n ) ) , O ( g ( n ) ) } T_1(n)+T_2(n)=\max\{O(f(n)),O(g(n))\} T1​(n)+T2​(n)=max{O(f(n)),O(g(n))} 。

  证明： 如果 $T_1(n)=O(f(n))$ ，那么存在正常数 $c_1$ 和 $n_1$ ，使得当 $n\ge n_1$ 时， $T_1(n)\le c_{1}f(n)$ 。

  如果 $T_2(n)=O(g(n))$ ，那么存在正常数 $c_2$ 和 $n_2$ ，使得当 $n\ge n_2$ 时， $T_2(n)\le c_{2}g(n)$ 。

  令 n 0 = max ⁡ { n 1 , n 2 } n_0=\max\{n_1,n_2\} n0​=max{n1​,n2​} ， c = max ⁡ { c 1 , c 2 } c=\max\{c_1,c_2\} c=max{c1​,c2​} 。

  如果对于 $n\ge n_0$ ， $f(n)\ge g(n)$ ，那么 $T_1(n)+T_2(n)\le c_{1}f(n)+c_{2}g(n)\le c(f(n)+g(n))\le 2cf(n)$ 。所以 $T_1(n)+T_2(n)=O(f(n))$ 。

  如果对于 $n\ge n_0$ ， $g(n)\ge f(n)$ ，那么 $T_1(n)+T_2(n)\le c_{1}f(n)+c_{2}g(n)\le c(f(n)+g(n))\le 2cg(n)$ 。所以 $T_1(n)+T_2(n)=O(g(n))$ 。

  一般来说， T 1 ( n ) + T 2 ( n ) = max ⁡ { O ( f ( n ) ) , O ( g ( n ) ) } T_1(n)+T_2(n)=\max\{O(f(n)),O(g(n))\} T1​(n)+T2​(n)=max{O(f(n)),O(g(n))} 。

  这意味着当两个算法的时间复杂度分别为 $T_1(n)$ 和 $T_2(n)$ 时，它们依次执行的总时间复杂度取决于两者中复杂度较高的那个。例如，若一个算法的时间复杂度为 $O(n)$ ，另一个算法的时间复杂度为 $O(n^2)$ ，当这两个算法依次执行时，总时间复杂度为 $O(n^2)$ 。

• 求积定理： $T_1(n)\cdot T_2(n)=O(f(n)\cdot g(n))$ 。

  如果 $T_1(n)=O(f(n))$ 且 $T_2(n)=O(g(n))$ 。

  存在正常数 $c_1$ 、 $n_1$ 、 $c_2$ 、 $n_2$ ，使得当 $n\ge n_1$ 时， $T_1(n)\le c_{1}f(n)$ ，当 $n\ge n_2$ 时， $T_2(n)\le c_{2}g(n)$ 。

  令 n 0 = max ⁡ { n 1 , n 2 } n_0=\max\{n_1,n_2\} n0​=max{n1​,n2​} ， $c=c_1{c}_2$ 。当 $n\ge n_0$ 时， $T_1(n)\cdot T_2(n)\le c_{1}f(n)\cdot c_{2}g(n)=c(f(n)\cdot g(n))$ 。所以 $T_1(n)\cdot T_2(n)=O(f(n)\cdot g(n))$ 。

  例如，如果一个算法的时间复杂度是 $O(n)$ ，另一个算法对每个输入执行该算法 $n$ 次，那么总时间复杂度是 $O(n\cdot n)=O(n^2)$ 。

大 O 记号的注意事项

在使用大 O 记号时，需要注意以下几点：

• 不要写成 $T(n)=O(2n^2)$ 或 $T(n)=O(n^2+n)$ 这种不规范的形式。根据大 O 记号的性质，正确的表示应该是 $T(n)=O(n^2)$ 。

• 大 O 记号的定义中已经隐含了不等关系，所以不需要写成 $T(n)\le O(f(n))$ ，这种写法是多余的。

• $T(n)\ge O(f(n))$ 的表示是错误的，没有任何意义。大 O 记号主要用于描述函数的上界，即算法运行时间的最长情况。