渐进符号

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

这些记号并不是计算机科学家发明的，而是二十世纪初用于数论领域。高德纳（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))$ 等价于存在常量 $c1,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)$ 但是不是 $O(n^{k-1})$。前者也说明大 $O$ 记号会忽略低阶项。

令 $$T(n)=a_nn^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 cf(n)$。这里我们选择 $$n_0=1,c=|a_k|+|a_{k-1}|+\cdots+|a_1|+|a_0|$$ 从 $T(n)$ 定义开始，每一项系数 $a_i$ 取绝对值，那么得到 $$T(n)\leq |a_n|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_n|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|)\\ &=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$ 使得所有 $n\geq n_0$ 都有 $$n^k\leq cn^{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$。

指数上乘一个常量

如果 $$T(n)=2^{nk}$$ 那么 $T(n)$ 不是 $O(2^n)$。 证明：这里仍旧使用反证法。假设 $T(n)=O(2^n)$，那么存在 $n_0,c$ 使得 $$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$。