形式陈述

$f(n)=O(g(n))$$f(n)=O(g(n))$ 表示存在常数 $c>0,n_0$$c>0,n_0$，使所有 $n\ge n_0$$n\ge n_0$ 满足 $0\le f(n)\le c g(n)$$0\le f(n)\le cg(n)$。若同时有 $f=O(g)$$f=O(g)$ 与 $g=O(f)$$g=O(f)$，记作 $f=\Theta(g)$$f=\mathrm{\Theta }(g)$。

直觉

渐近记号只关心规模足够大后的增长等级，把实现速度、机器常数和有限前缀从结构性比较中剥离。

例子与边界

$3n^2+5n+7=\Theta(n^2)$$3n^2+5n+7=\mathrm{\Theta }(n^2)$。$O$$O$ 是上界集合而非精确等号；说某算法是 $O(n^2)$$O(n^2)$ 不排除它实际也是 $O(n)$$O(n)$。

推论与应用

它用于描述算法时间与空间、递推式、概率尾界以及复杂度类的资源上界。

参考资料

• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 3.
• Donald E. Knuth, “Big Omicron and Big Omega and Big Theta,” 1976.