第2章算法分析：大O符号的定义和性质

2.3 大 O 符号

2.3.1 大 O 符号的定义

大 O 符号（Big O notation），又称为渐近符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

大 O 符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。之后经另一位德国数论学家爱德蒙·兰道的著作得到推广，因此它有时又称为兰道符号（Landau symbols）。代表“order of …”（……阶）的大 O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写英文字母“O”。

大 O 符号的本质是函数渐近行为的极限描述，其形式化定义：

给定两个定义在实数某子集上的关于 $x$ 的函数 $f(x)$ 和 $g(x)$ ，当 $x$ 趋近于无穷大时，存在正实数 $M$ ，使得对于所有充分大的 $x$ ，都有$f(x)$ 的绝对值小于等于 $M\times g(x)$ 的绝对值，那么我们就可以说，当 $x\to \infty$ 时，
$$f(x)=O(g(x))$$
也就是说，假如存在正实数 $M$ 和实数 $x_0$ ，使得对于所有的 $x\ge x_0$ ，均有：$|f(x)|\le M|g(x)|$ 成立，我们就可以认为 $f(x)=O(g(x))$ 。在很多情况下，会省略“当 $x$ 趋近于无限大时”这个前提。

上述定义，用极限来表示：
$$当且仅当\underset{x\to \infty }{\lim }\left|\frac{f(x)}{g(x)}\right|<\infty 时，有f(x)=O(g(x))$$
也就是，当 $x\to \infty$ 时，$\frac{f(x)}{g(x)}$ 有上界，极限值为有限常数或未达无穷大。

例 1： 证明 $T(n)=3n^2+5n+2$ 是 $O(n^2)$ 。

证明：

$$\underset{n\to \infty }{\lim }\frac{3n^2+5n+2}{n^2}=\underset{n\to \infty }{\lim }\left(3+\frac{5}{n}+\frac{2}{n^2}\right)=3(有限正常数)$$
因为极限存在且为有限值，所以 $T(n)=O(n^2)$ 。

2.3.2 大 O 符号的性质

以下是大 O 符号的主要性质及其证明。证明中假设所有函数定义在自然数上，且 $f(n)$ 非零（或仅在有限点为零）。

性质 1：（自反性）对于任意函数 $f(n)$，有 $f(n)=O(f(n))$。

证明：

取常数 $c=1$ 和 $n_0=1$。则对于所有 $n\ge n_0$，有：$|f(n)|\le 1\cdot |f(n)|$ 。根据大 O 定义，这直接表明 $f(n)=O(f(n))$ 。

性质 2：（传递性）如果 $f(n)=O(g(n))$ 和 $g(n)=O(h(n))$，则 $f(n)=O(h(n))$。

证明：

由 $f(n)=O(g(n))$，存在常数 $c_1>0$ 和 $n_1$ 使得对于所有 $n\ge n_1$，有：$|f(n)|\le c_1\cdot |g(n)|$ 。

由 $g(n)=O(h(n))$，存在常数 $c_2>0$ 和 $n_2$ 使得对于所有 $n\ge n_2$，有：$|g(n)|\le c_2\cdot |h(n)|$ 。

取 $n_0=\max (n_1,n_2)$ 和 $c=c_1\cdot c_2$。则对于所有 $n\ge n_0$，有：
$$|f(n)|\le c_1\cdot |g(n)|\le c_1\cdot (c_2\cdot |h(n)|)=(c_1{c}_2)\cdot |h(n)|=c\cdot |h(n)|.$$
因此， $f(n)=O(h(n))$.

性质 3：（常数倍性质）如果 $f(n)=O(g(n))$ 且 $k$ 是一个常数（即 k∈R∖{0}k \in \mathbb{R} \setminus \{0\}k∈R∖{0}，但 $k=0$ 时平凡成立），则 $k\cdot f(n)=O(g(n))$。

证明：

由 $f(n)=O(g(n))$，存在常数 $c_1>0$ 和 $n_1$ 使得对于所有 $n\ge n_1$，有：$|f(n)|\le c_1\cdot |g(n)|.$

取 $c=|k|\cdot c_1$ 和 $n_0=n_1$。则对于所有 $n\ge n_0$，有：$|k\cdot f(n)|=|k|\cdot |f(n)|\le |k|\cdot (c_1\cdot |g(n)|)=(|k|c_1)\cdot |g(n)|=c\cdot |g(n)|$

因此， $k\cdot f(n)=O(g(n))$.

性质 4：（和的性质）如果 $f_1(n)=O(g_1(n))$ 和 $f_2(n)=O(g_2(n))$，则 $f_1(n)+f_2(n)=O(\max (|g_1(n)|,|g_2(n)|))$。更一般地，$f_1(n)+f_2(n)=O(|g_1(n)|+|g_2(n)|)$，且当 $g_1(n)$ 和 $g_2(n)$ 渐近非负时，可简化为 $O(\max (|g_1(n)|,|g_2(n)|))$。

证明：

由 $f_1(n)=O(g_1(n))$，存在常数 $c_1>0$ 和 $n_1$ 使得对于所有 $n\ge n_1$，有：$|f_1(n)|\le c_1\cdot |g_1(n)|$ .

由 $f_2(n)=O(g_2(n))$，存在常数 $c_2>0$ 和 $n_2$ 使得对于所有 $n\ge n_2$，有：$|f_2(n)|\le c_2\cdot |g_2(n)|$ 。

取 $n_0=\max (n_1,n_2)$ 和 $c=c_1+c_2$。定义 $g(n)=\max (|g_1(n)|,|g_2(n)|)$。注意到对于所有 $n$，有 $|g_1(n)|\le g(n)$ 和 $|g_2(n)|\le g(n)$。则对于所有 $n\ge n_0$，有：
$$|f_1(n)+f_2(n)|\le |f_1(n)|+|f_2(n)|\le c_1\cdot |g_1(n)|+c_2\cdot |g_2(n)|\le c_1\cdot g(n)+c_2\cdot g(n)=(c_1+c_2)\cdot g(n)=c\cdot g(n)$$
因此， $f_1(n)+f_2(n)=O(g(n))=O(\max (|g_1(n)|,|g_2(n)|))$。

此外，因为 $|g_1(n)|+|g_2(n)|\le 2\max (|g_1(n)|,|g_2(n)|)$，所以 $f_1(n)+f_2(n)=O(|g_1(n)|+|g_2(n)|)$ 也成立。

性质 5：（乘积性质）如果 $f_1(n)=O(g_1(n))$ 和 $f_2(n)=O(g_2(n))$，则 $f_1(n)\cdot f_2(n)=O(g_1(n)\cdot g_2(n))$。

证明：

由 $f_1(n)=O(g_1(n))$，存在常数 $c_1>0$ 和 $n_1$ 使得对于所有 $n\ge n_1$，有：$|f_1(n)|\le c_1\cdot |g_1(n)|$。同理可得：$|f_2(n)|\le c_2\cdot |g_2(n)|$ 。

取 $n_0=\max (n_1,n_2)$ 和 $c=c_1\cdot c_2$。则对于所有 $n\ge n_0$，有：$|f_1(n)\cdot f_2(n)|=|f_1(n)|\cdot |f_2(n)|\le (c_1\cdot |g_1(n)|)\cdot (c_2\cdot |g_2(n)|)=(c_1{c}_2)\cdot |g_1(n)\cdot g_2(n)|=c\cdot |g_1(n)\cdot g_2(n)|$ 。

因此， $f_1(n)\cdot f_2(n)=O(g_1(n)\cdot g_2(n))$.

性质 6：（多项式性质）如果 $f(n)$ 是一个 $k$ 次多项式，即 $f(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0$（其中 $a_k\ne 0$)，则 $f(n)=O(n^k)$。

证明：

对于足够大的 $n$（例如 $n\ge 1$)，有 $|n^i|\le |n^k|$ 对所有 $i\le k$ 成立。因此：
$$|f(n)|\le |a_k||n^k|+|a_{k-1}||n^{k-1}|+\cdots +|a_0|\le |a_k||n^k|+|a_{k-1}||n^k|+\cdots +|a_0||n^k|=\left(\sum _{i=0}^k|a_i|\right)|n^k|$$
取 $c={\sum }_{i=0}^k|a_i|$ 和 $n_0=1$。则对于所有 $n\ge n_0$，有 $|f(n)|\le c\cdot |n^k|$，所以 $f(n)=O(n^k)$.

性质 7：（对数性质）对于底数 $b>1$ 和 $a>0$，有 ${\log }_{b}n=O({\log }_{2}n)$，且更一般地，$({\log }_{b}n{)}^a=O(n^{ϵ})$ 对于任意 $ϵ>0$（即对数函数增长慢于任何正幂函数）。

证明：

• 部分 1： ${\log }_{b}n=O(\log n)$。

  由对数换底公式，${\log }_{b}n=\frac{\ln n}{\ln b}$。取 $c=\frac{1}{|\ln b|}$（因为 $b>1$，所以 $\ln b>0$) 和 $n_0=1$。则对于所有 $n\ge n_0$，有：
  $$|{\log }_{b}n|=\left|\frac{\ln n}{\ln b}\right|=\frac{|\ln n|}{|\ln b|}\le c\cdot |\ln n|$$
  因此， ${\log }_{b}n=O(\log n)$（这里 $\log n$ 表示自然对数）。

• 部分 2： $({\log }_{b}n{)}^a=O(n^{ϵ})$ 对于任意 $ϵ>0$。

  这可以通过极限或 L’Hôpital 法则证明。考虑极限：${\lim }_{n\to \infty }\frac{({\log }_{b}n{)}^a}{n^{ϵ}}$ ，

  令 $t={\log }_{b}n$，则 $n=b^t$，当 $n\to \infty$ 时 $t\to \infty$，极限变为：
  $$\underset{t\to \infty }{\lim }\frac{t^a}{(b^t{)}^{ϵ}}=\underset{t\to \infty }{\lim }\frac{t^a}{b^{ϵt}}.$$
  由于指数函数增长快于多项式函数，该极限为 0。因此，存在 $n_0$ 使得对于所有 $n\ge n_0$，有 $\frac{({\log }_{b}n{)}^a}{n^{ϵ}}\le 1$，即 $|({\log }_{b}n{)}^a|\le 1\cdot |n^{ϵ}|$。所以 $({\log }_{b}n{)}^a=O(n^{ϵ})$.

注意：

• 大 O 符号不具有对称性：即 $f(n)=O(g(n))$ 不一定意味着 $g(n)=O(f(n))$。如果两者同时成立，则记作 $f(n)=\Theta (g(n))$（Theta 符号），表示 $f$ 和 $g$ 有相同的渐近增长率。

• 大 O 符号关注上界，且忽略常数因子和低阶项，这使其适用于描述大规模输入下的性能。

• 不要写成 $T(n)=O(2n^2)$ 或 $T(n)=O(n^2+n)$ 。这两种的正确表示是 $T(n)=O(n^2)$ 。

• 不表示 $T(n)\le O(f(n))$ ，因为对大 O 记号的定义中已经隐含了不等关系。

• $T(n)\ge O(f(n))$ 的表示是错误的，没有意义。

大 O 符号体现了对函数总体渐进趋势的关注和刻画，在后续进行算法时间复杂度和空间复杂度分析中将大显身手。

以上一直在书写大 O 符号，如果用口语表达，怎么读？以 $O(n)$ 为例，可以读作“大 O n”，也可以读作 “O n”。