本文来介绍一下描述复杂度的渐进记号,渐进记号不仅可以用来描述时间复杂度,也可以用来描述空间复杂度,甚至可以描述和算法没有任何关系的函数.

\Theta记号

前面介绍了插入排序的时间复杂度为\Theta (n^2).它是取的二次函数f(n) = an^2+bn+c的最高次项.也就是说有下面的公式成立:

c_1n^2 \leq an^2+bn+c \leq c_2n^2

正式的定义为:

\Theta (g(n)) = \{f(n):存在正常量c_1,c_2和n_0,使得对所有n\geq n_0,有0\leq c_1g(n)\leq f(n)\leq c_2g(n)\}

image.png

O记号

\Theta记号给出了一个函数的上界和下界,而O记号仅给出函数的上界,定义为:

O(g(n)) = \{f(n):存在正常量c和n_0,使得对所有n\geq n_0,有0\leq f(n)\leq cg(n)\}

O记号仅定义了上界,比\Theta记号宽松,所以\Theta (g(n)) \subseteq O(g(n))

\Omega记号

如果仅给出函数的下界,可以使用\Omega记号,定义为:

\Omega(g(n)) = \{f(n):存在正常量c和n_0,使得对所有n\geq n_0,有0\leq cg(n)\leq f(n)\}

由此可知,\Theta (g(n))介于于\Omega(g(n))O(g(n))

o记号

O记号提供的渐近上界可能是也可能不是渐近紧确的.界2 n ^ { 2 } = O \left( n ^ { 2 } \right)是渐近紧确的,但是界2 n = O \left( n ^ { 2 } \right)却不是.我们使用o记号来表示一个非渐近紧确的上界.形式化的定义为:

o(g(n)) = \{f(n):对任意正常量c>0,存在常量n_0>0,使得对所有n\geq n_0,有0\leq f(n)< cg(n)\}

由此可知,\Theta (g(n))介于于\Omega(g(n))O(g(n))

\omega记号

\omega记号与\Omega记号的关系类似o记号于O记号的关系.我们使用\omega记号来表示一个非渐近紧确的下界.形式化的定义为:

\omega(g(n)) = \{f(n):对任意正常量c>0,存在常量n_0>0,使得对所有n\geq n_0,有0\leq cg(n)< f(n)\}

下图是这5种标记的关系:
image.png

posted @ 2019-02-03 17:14:45
评论加载中...

发表评论