渐进符号

算法分析离不开渐进符号，它能帮助我们去除常量、低阶量对分析的影响，同时在大规模输入时帮助分析比较两种算法的优劣。

这些记号并不是计算机科学家发明的，而是在二十世纪初用于数论领域。高德纳（Donald E. Knuth）提议将其用于算法分析。

下面先介绍最常见的大 $O$ 记号，然后介绍大 $\Omega$、大 $\Theta$ 和小 $o$ 记号。

大 $O$ 记号

大 $O$ 记号（Big-O Notation）

$T(n)=O(f(n))$ 等价于存在常量 $c>0,n_0>0$ 使得对所有 $n\geq n_0$ 都有 $$T(n)\leq cf(n)$$

注意，这里的 $c,n_0$ 是不依赖于 $n$ 的常量。

大 $O$ 定义了上界，“小于等于”的语义。

大 $\Omega$ 记号

大 $\Omega$ 记号（Big-Omega Notation）

$T(n)=\Omega(f(n))$ 等价于存在常量 $c>0,n_0>0$ 使得对所有 $n\geq n_0$ 都有 $$T(n)\geq cf(n)$$

大 $\Omega$ 定义了下界，“大于等于”的语义。

大 $\Theta$ 记号

大 $\Theta$ 记号（Big-Theta Notation）

$T(n)=\Theta(f(n))$ 等价于存在常量 $c_1,c_2>0,n_0>0$ 使得对所有 $n\geq n_0$ 都有 $$c_1f(n)\leq T(n)\leq c_2f(n)$$

大 $\Theta$ 同时定义了上下界，“等于”的语义。

小 $O$ 记号

小 $O$ 记号（Little-O Notation）

$T(n)=o(f(n))$ 等价于对所有常量 $c>0$，都存在 $n_0>0$ 使得对所有 $n\geq n_0$ 都有 $$T(n)\leq cf(n)$$

与大 $O$ 记号不同，这里要求对所有 $c>0$ 都要成立，而不是找到一个即可。如果大 $O$ 记号表示“小于等于”的语义，那么小 $o$ 表示的就是“严格小于”的语义。

示例

多项式 $T(n)$

下面给出一个具体的例子，说明次数至多为 $k$ 的多项式 $T(n)$ 是 $O(n^k)$，而 $n^k$ 不是 $O(n^{k-1})$。前者也说明大 $O$ 记号会忽略低阶项。

令 $$T(n)=a_kn^k+a_{k-1}n^{k-1}+\cdots+a_1n+a_0$$ 其中 $k\geq 0$ 是整数，$a_i\ (i\in\{0,1,2,\cdots,k\})$ 是实数，那么 $$T(n)=O(n^k)$$ 证明：根据定义，关键在于找到 $c,n_0$ 使得 $T(n)\leq cn^k$。这里选择 $$n_0=1,\quad c=|a_k|+|a_{k-1}|+\cdots+|a_1|+|a_0|$$ 对 $T(n)$ 的每一项取绝对值，得到 $$T(n)\leq |a_k|n^k+|a_{k-1}|n^{k-1}+\cdots+|a_1|n+|a_0|$$ 由于 $n\geq 1$ 且 $k\geq 0$，有 $n^k\geq n^i$，其中 $i\in\{0,1,2,\cdots,k\}$，因此 $$\begin{aligned} T(n)&\leq |a_k|n^k+|a_{k-1}|n^k+\cdots+|a_1|n^k+|a_0|n^k\\ &=n^k(|a_k|+|a_{k-1}|+\cdots+|a_1|+|a_0|)\\ &\leq cn^k \end{aligned}$$ 证毕。

如果 $k\geq 1$ 是整数，且 $T(n)=n^k$，那么 $T(n)$ 不是 $O(n^{k-1})$。 证明：使用反证法。假设 $T(n)=O(n^{k-1})$，那么存在 $n_0,c>0$，使得对所有 $n\geq n_0$ 都有 $$n^k\leq cn^{k-1}$$ 两边同时除以 $n^{k-1}$，得到 $$n\leq c$$ 这表明常数 $c$ 大于等于任意大的整数，矛盾。证毕。

指数上加一个常量

如果 $$T(n)=2^{n+k}$$ 其中 $k$ 是常量，那么 $$T(n)=O(2^n)$$ 证明： $$2^{n+k}=2^k2^n$$ 因此，取 $n_0=1,c=2^k$，有 $T(n)\leq c2^n,n\geq n_0$。

指数上乘一个常量

如果 $k>1$，且 $$T(n)=2^{nk}$$ 那么 $T(n)$ 不是 $O(2^n)$。 证明：仍使用反证法。假设 $T(n)=O(2^n)$，那么存在 $n_0,c>0$，使得对所有 $n\geq n_0$ 都有 $$2^{nk}\leq c2^n$$ 那么 $$2^{n(k-1)}\leq c$$ 当 $n$ 趋于无穷大时，左侧趋于无穷大，不可能始终不大于常量 $c$，矛盾。

最大值

令 $f,g$ 是从正整数到非负实数的函数。对 $n\geq 1$，令 $$T(n)=\max\{f(n),g(n)\}$$ 那么 $$T(n)=\Theta(f(n)+g(n))$$ 证明：我们需要找到 $c_1,c_2,n_0$ 使得 $$c_1(f(n)+g(n))\leq T(n)\leq c_2(f(n)+g(n))$$ 由于 $f(n)$ 和 $g(n)$ 非负， $$\max\{f(n),g(n)\}\leq f(n)+g(n)\leq 2\max\{f(n),g(n)\}$$ 变换得到 $$\frac{1}{2}(f(n)+g(n))\leq \max\{f(n),g(n)\}\leq f(n)+g(n)$$ 因此，根据定义可取 $c_1=\frac{1}{2},c_2=1,n_0=1$。