关于算法复杂度的那些记号和它们的含义

O (最坏时间复杂度):
O 给出一个函数的上界(upper bound),在算法里面表示的就是最坏情况。符号的严格定义如下:对于给定一个函数 g(n)O(g(n)) 表示以下函数的集合

O(g(n)) = \{f(n):?????c?n_0??????n\ge n_0??0\le f(n)\le cg(n)\}


现在解释上面数学定义的含义,例如我们平时说的 O(n^2)O(\log n) 表示的是两个函数集合或者函数族,表示的是两类函数,而我们分析具体算法的时候,它们的运行时间是具体的一个函数,这些函数都属于某些函数集合。假设有A算法的运行时间为 2n^2 ,那么这个算法的时间复杂度我们就说是 O(n^2) ,这句话的意思其实是说 T(n)=2n^2 这个函数是 O(n^2) 集合中的一个元素,也就是 2n^2 \in O(n^2) ,不过现实中我们表示算法复杂度时经常用“ = ”代替“ \in ”,记作 2n^2 = O(n^2)
另外还有一点需要注意的是,虽然根据它的定义如果 f(n) = O(g(n)) ,对于所有的 h(n) \ge g(n) 都有 f(n) = O(h(n)) ,例如 2n^2 = O(n^3) 这种说法也是正确的,但是我们日常里面说的 O 往往是所研究函数的紧确上界(tight upper bound),所有我们往往不说 2n^2 = O(n^3) 而是说 2n^2 = O(n^2) ,关于这个我在sof上提问过,有兴趣可以看
要证明一个函数是不是属于 O(g(n)) ,我们可以用它的定义去证,还是用上面的例子,证明 2n^2 属于 O(n^2) ,证明如下:

0\le 2n^2 \le cn^2(c,n \in R^+)


0\le 2 \le c


由以上可知存在着 c \ge 2?n_0 \gt 0 使得 0\le 2n^2 \le cn^2(c,n \in R^+) 成立,所以 2n^2 = O(n^2) ;也可以利用定义证明 2n^2 \neq O(n) ,证:

0\le 2n^2 \le cn(c,n \in R^+)


0\le 2 \le c/n


可知在 (0,c/2] 的区间内公式成立,但在 (c/2,\infty) 上并不成立,顾不存在一个左边界 n_0 满足对于所有 n\ge n_0??0\le f(n)\le cg(n) ,所以 2n^2 \neq O(n)
\Theta
\Theta 给出一个函数的紧确界(tight bound),符号的严格定义如下:对于给定一个函数 g(n)\Theta(g(n)) 表示以下函数的集合

\Theta(g(n)) = \{f(n):?????c_1?c_2?n_0??????n\ge n_0??0\le c_1g(n) \le f(n)\le c_2g(n)\}


O 表示的是在 n \ge n_0 的情况下 f(n) 总是在 cg(n) 的下面, \Theta 表示的是 f(n) 总是夹在 c_1g(n)c_2g(n) 的中间,上面例子中的 2n^2 = O(n^3) 但是 2n^2 \neq \Theta(n^3) 。证明如下:
采用反证法,假设存在正常量 c_1 和正常量 n_0 满足左公式

c_1n^3 \le 2n^2


c_1n \le 2


c_1 为正常量,对于任意大的 n 此式不可能成立,所以 2n^2 \neq \Theta(n^3)
\Omega (最好时间复杂度):
\Omega 给出一个函数的下界(lower bound),在算法里面表示的就是最好情况。符号的严格定义如下:对于给定一个函数 g(n)\Omega(g(n)) 表示以下函数的集合

\Omega(g(n)) = \{f(n):?????c?n_0??????n\ge n_0??0 \le cg(n) \le f(n)\}


日常使用并不多,如果使用的话也是和使用大 O 那样的情况,虽然定义里面的 \Omega 可能是紧确(tight)的或者非紧确的,但是日常用的话也是大多数用来指明紧确的下界
还有三个很少很少用的符号分别是上面三个字母的小写 o, \omega, \theta ,因为太少用我这里就不说了,在CLRS里面有所介绍,想看的话就去看CLRS吧

references:

[1] introduction to algorithm
[2] sof上的提问