大 O、大 Omega、大 Theta 的区别，O(n) 复杂度是什么意思

1 O、Ω、Θ 的定义

在数学、算法分析里，$O$、$\mathrm{\Omega }$、$\mathrm{\Theta }$ 都是在描述两个函数的渐近增长速度，通常讨论 $n\to \mathrm{\infty }$ 时的关系。

最核心的区别是：

$$\boxed{{\displaystyle O=\text{渐近上界},\mathrm{\Omega }=\text{渐近下界},\mathrm{\Theta }=\text{同阶/紧确渐近界}}}$$

更严格地说，给定两个非负函数 $f(n)$ 和 $g(n)$。

• $f(n)=O(g(n))$：存在常数 $c>0,n_0$，使得对所有 $n\ge n_0$，

  $$f(n)\le cg(n).$$

  意思是：$f$ 最终不会比 $g$ 快超过一个常数倍。

• $f(n)=\mathrm{\Omega }(g(n))$：存在常数 $c>0,n_0$，使得对所有 $n\ge n_0$，

  $$f(n)\ge cg(n).$$

  意思是：$f$ 最终至少有 $g$ 这么快的增长量级。

• $f(n)=\mathrm{\Theta }(g(n))$：存在常数 $c_1,c_2>0,n_0$，使得对所有 $n\ge n_0$，

  $$c_{1}g(n)\le f(n)\le c_{2}g(n).$$

  也就是：

  $$f(n)=O(g(n))\text{且}f(n)=\mathrm{\Omega }(g(n)).$$

  意思是：$f$ 和 $g$ 的增长速度是同一个数量级。

可以这样记：

符号	含义	直觉
$O(g(n))$	上界	“最多这么快”
$\mathrm{\Omega }(g(n))$	下界	“至少这么快”
$\mathrm{\Theta }(g(n))$	上下界一致	“就是这个量级”

如果画成一种直观的“夹住”关系：

$$\begin{array}{rl}f(n)=O(g(n))& ⟹f(n)\text{在上面被 }g(n)\text{ 的常数倍压住},\\ f(n)=\mathrm{\Omega }(g(n))& ⟹f(n)\text{在下面被 }g(n)\text{ 的常数倍托住},\\ f(n)=\mathrm{\Theta }(g(n))& ⟹f(n)\text{被 }g(n)\text{ 的两个常数倍夹住}.\end{array}$$

2 举例

比如 $f(n)=3n^2+10n+100$，那么：

$$f(n)=O(n^2),$$

因为它最终不会超过某个常数倍的 $n^2$。

同时：

$$f(n)=\mathrm{\Omega }(n^2),$$

因为它最终也至少是某个常数倍的 $n^2$。

因此，我们有：

$$\boxed{{\displaystyle f(n)=\mathrm{\Theta }(n^2)}}.$$

注意，这里有一个容易混淆的点：我们常用的大 $O$ 不等于“精确复杂度”。例如，上面的函数不仅有 $f(n)=O(n^2)$，也完全可以说

$$f(n)=O(n^3),f(n)=O(n^4),f(n)=O(2^n).$$

这些都没错，因为它们都是上界，只是比较松。

相反，$f(n)=\mathrm{\Theta }(n^2)$ 表达的信息更强：它明确告诉你真正的渐近数量级就是 $n^2$。

再举一个例子，例如：

$$n=O(n^2),$$

是对的，因为

$$n\le n^2$$

在 $n\ge 1$ 时成立。

但是

$$n\ne \mathrm{\Theta }(n^2),$$

因为 $n$ 和 $n^2$ 并不是同一个增长量级。

反过来：

$$n^2=\mathrm{\Omega }(n),$$

也是正确的。

3 另外一个判断方式：看 n → ∞ 的极限

另外一个很有用的判断方式是看极限。如果

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=L,0<L<\mathrm{\infty },$$

那么通常可以直接得到

$$\boxed{{\displaystyle f(n)=\mathrm{\Theta }(g(n))}}.$$

例如：

$$\underset{n\to \mathrm{\infty }}{lim}\frac{3n^2+10n+100}{n^2}=3,$$

所以

$$3n^2+10n+100=\mathrm{\Theta }(n^2).$$

在算法里，如果一个程序运行时间是

$$T(n)=5n^2+3n+10,$$

最准确的渐近描述通常是

$$T(n)=\mathrm{\Theta }(n^2),$$

而说 $T(n)=O(n^2)$ 只是给出了它的上界。