时间复杂度表示法——OΩΘoω
A6n6d6y6
·
·
算法·理论
时间复杂度表示法——OΩΘoω
概述
$\Omega$，读音：big-omega；**表示下界(大于等于)**
$\rm{o}$，读音：small-o；**表示上界(小于)**
$\omega$，读音：small-omega；**表示下界(大于)**
$\Theta$，读音：theta；既是上界也是下界，称为**确界**。
在表示一个算法时间复杂度时，我们常用如$\rm T(n)=\rm O(n^2)$的形式表示，而在渐进分析中的 “$=$” 更倾向于 “$\in$” 的意思。
举个例子：渐进表达式$f(n) =\rm O(g(n)) $所表达的意思是$\rm O(g(n)) = [f(n),h(n),…,g(n)],f(n)\in O(g(n))$。
## 大O表示法
一般用于界定函数集合的上界，渐进表达式$\rm O(g(n))$的含义就是，$c$为正常数，函数集合$\rm O$中的元素的最大值不会超过$c\times g(n)$。$f(n) = \rm O(g(n))$的含义是，函数$f(n)$属于集合$O(g(n))$，因为函数集合$O$中的最大值为$c\times g(n)$，所以$f(n)$的最大值为$c\times g(n)$。由于只是渐进的上界，所以当函数的阶数越小时，上界越紧确。
算法导论中这样描述大$\rm O$表示法：
> 当函数的大小只有上界，没有明确下界的时候，则可以使用大$\rm O$表示法。$f(n) = \rm O(g(n))$正式的数学定义：存在正常数$c,n,n_0$，当$n>n_0$时，对于任意的$f(n)$符合$0\le f(n)\le c\times g(n)$。
直观视觉图如下：
## 大Ω表示法
一般用于界定函数集合的下界，渐进表达式$\Omega(g(n))$的含义就是，$c$为正常数，函数集合$\Omega$中的元素的最小值不会低于$c\times g(n)$。$f(n) = \Omega(g(n))$的含义是，函数$f(n)$属于集合$\Omega(g(n))$，因为函数集合$\Omega$中的最小值为$c\times g(n)$，所以$f(n)$的最小值为$c\times g(n)$。由于只是渐进的界，所以当函数的阶数越小时，下界越紧确。
算法导论中这样描述大O表示法：
> 当函数的大小只有下界，没有明确上界的时候，则可以使用大O表示法。$f(n) = \rm O(g(n))$正式的数学定义：存在正常数$c,n,n_0$，当$n>n_0$时，对于任意的$f(n)$符合$0\le c\times g(n)\le f(n)$。
直观视觉图如下：
## 大Θ表示法
用于界定函数的渐进上界和渐进下界。当$f(n)=\Theta(g(n))$的时候，代表着$g(n)$为$f(n)$的渐进确界。而$\Theta$渐进描述符在所有的渐进描述符中是最严格的一个，因为它既描述了函数的上界，有描述了函数的下界。
算法导论中是如何描述$\Theta$表示法的。
> $f(n)$= $\Theta(c\times g(n))$正式的数学定义：存在正常数$c1,c2,n,n_0$，当$n>n_0$的时，对于任意的$f(n)$对符合$c1\times g(n)\le f(n)\le c2\times g(n),c1\times g(n),c2.g(n)$都是渐进正函数(当n趋于无穷大的时候，$f(n)$为正)。
直观视觉图如下所示：
算法导论中还根据大$\rm O$，大$\Omega$，$\Theta$的定义得到一个定理：
当且仅当函数$f(n)=\rm O(g(n)) and f(n)=\Omega(g(n))时，f(n)=\Theta(g(n))
小o表示法
大O表示法所描述的界，可以是渐进紧确的，也可以是非渐进紧确的。而小o表示法所描述的界是非渐进紧确的。下面是小o表示法的数学定义：
函数f(n)=\rm o(g(n))对于任意的正常数c，存在常数n_0>0，使得对所有的n_0>0都存在0\le f(n)\le c\times g(n)。
这里可以根据定义看出同样是0\le f(n)\le c\times g(n)，大O表示法是存在一个常数c符合该条件，而小o表示法是对于所有的正常数c都符合该条件。所以当n趋于无穷大，c也趋于无穷大的时候，小\rm o表示法描述的界的宽松范围比大\rm O表示法描述的界宽松范围大最少一个次方，所以小o表示法所描述的界必然是渐进非紧确的。
小ω表示法
与大\rm O表示法与小\rm o表示法的区别类似，大\Omega表示法所描述的界，可以是渐进紧确的，也可以是非渐进紧确的。而小\omega表示法所描述的界是非渐进紧确的。下面是小\omega表示法的数学定义：
函数f(n)=\omega(g(n))对于任意的正常数c，存在常数n_0>0，使得对所有的n_0>0都存在0\le c\times g(n)\le f(n)。
函数间的特性和比较
在后续的实际算法分析中，会经常使用到以上五种描述符，这里也说一下它们之间的比较关系和特性，方便以后做分析时，理解公式的推演过程。
传递性：
-
f(n) = \Theta(g(n))$和$g(n) = θ(h(n))$可以得出$f(n) = \Theta(h(n))
-
f(n) = \rm O(g(n))$和$g(n) = \rm O(h(n))$可以得出$f(n) = \rm O(h(n))
-
f(n) = \Omega(g(n))$和$g(n) = \Omega(h(n))$可以得出$f(n) = \Omega(h(n))
-
\rm f(n) = o(g(n))$和$g(n) = \rm o(h(n))$可以得出$f(n) = \rm o(h(n))
-
f(n) = \omega(g(n))$和$g(n) = \omega(h(n))$可以得出$f(n) = \omega(h(n))
自反性：
-
f(n)=\Theta(f(n))$可以得出$f(n) = O(f(n))$和$f(n) = \Omega(f(n))
对称性：
-
f(n)=\Theta(g(n))$当且仅当$g(n)=\Theta(f(n))
转置对称性：
-
f(n) = O(g(n))$当且仅当$g(n) =\Omega(f(n))
-
f(n) = o(g(n))$当且仅当$g(n) =\omega(f(n))
下面是关于这五种渐进符号在视觉上的直观的比较关系：
对于常见大\rm O表示法的时间复杂度如下表所示
| 实例 |
阶 |
名称 |
| 12 |
\rm O(1) |
常数 |
| 2n+12 |
\rm O(n) |
线性 |
| 3n^2+2n+12 |
\rm O(n^2) |
平方 |
| 5\log_2n+20 |
\rm O(\log n) |
对数 |
| 2n+3n\log_2n+20 |
\rm O(n\log n) |
线性对数 |
| 2^n |
\rm O(2^n) |
指数 |
| n! |
\rm O(n!) |
阶乘 |
所耗时间从小到大依次排列为：
O(1)\le O(\log n)\le O(\sqrt{n})\le O(n)\le O(n\log n)\le O(n\sqrt{n})\le O(n^2)\le O(n^3)\le O(2^n)\le O(n!)\le O(n^n)
例子
在这篇题解中，时间复杂度的分析使用的是\Theta表示，请读者写出其余四种表示方法下的时间复杂度
参考资料
算法分析——算法的渐进效率分析 和 渐进符号大O、大Ω、大θ、小o、小ω
算法分析与时间复杂度
算法时间复杂度分析——大O、大Ω、大θ、小o，小ω