前言
本篇文章收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。
你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。
后面几节，咱们一起学习了算法的复杂度如何剖析，并从最坏、均匀、最好以及不能应用最坏状况全方位无死角的分析了算法的复杂度，在咱们示意复杂度的时候，通常应用大O来示意。
然而，在其余书籍中，你可能还见过Θ、Ω、o、ω等符号。
那么，这些符号又是什么意思呢？
本节，咱们就来解决这个问题。
读音
咱们先来纠正一波读音：
- O，/əʊ/，大Oh
- o，/əʊ/，小oh
- Θ，/ˈθiːtə/，theta
- Ω，/oʊˈmeɡə/，大Omega
- ω，/oʊˈmeɡə/，小omega
是不是跟老师教得不太一样^^
数学解释
Θ
Θ定义了一种准确的渐近行为（exact asymptotic behavior），怎么说呢？
用函数来示意：
对于f(n)，存在负数n0、c1、c2，使得当 n>=n0 时，始终存在 0 <= c1*g(n) <= f(n) <= c2*g(n)，则咱们能够用 f(n)=Θ(g(n))示意。用图来示意：
Θ同时定义了上界和下界，f(n)位于上界和下界之间，且蕴含等号。
比如说，f(n) = 2n^2+3n+1 = Θ(n^2)，此时，g(n)就是用f(n)去掉低阶项和常数项得来的，因为必定存在某个负数n0、c1、c2，使得 0 <= c1*n^2 <= 2n^2+3n+1 <= c2*n^2，当然，你说g(n)是2*n^2也没问题，所以，g(n)实际上满足这个条件的一组函数。
好了，如果Θ你能了解了，上面四个就好了解了。
O
O定义了算法的上界。
用函数来示意：
对于f(n)，存在负数n0、c，使得当 n>=n0 时，始终存在 0 <= f(n) <= c*g(n)，则咱们能够用 f(n)=O(g(n))示意。用图来示意：
O只定义上界，只有f(n)不大于c*g(n)，就能够说 f(n)=O(g(n))。
比如说，对于插入排序，咱们说它的工夫复杂度是O(n^2)，然而，如果用Θ来示意，则必须分成两条：
- 最坏的状况下，它的工夫复杂度为Θ(n^2)；
- 最好的状况下，它的工夫复杂度为Θ(n)。
这里的n^2只是g(n)这一组函数中最小的上界，当然，g(n)也能够等于n^3。
不过，咱们个别说复杂度都是指的最小的上界，比方，这里插入排序的工夫复杂度如果说是O(n^3)，从实践上来说，也没问题，只是不合乎约定罢了。
插入排序最好的状况就是数组自身就是有序的。
o
o定义的也是算法的上界，不过它不蕴含等于，是一种不准确的上界，或者称作松上界（某些书籍翻译为非紧上界）。
用函数来示意：
对于f(n)，存在负数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < c*g(n)，则咱们能够用 f(n)=o(g(n))示意。用图来示意：
o示意仅仅是大O去掉等于的状况，其余行为与大O截然不同。
Ω
Ω定义了算法的下界，与O正好相同。
用函数来示意：
对于f(n)，存在负数n0、c，使得当 n>=n0 时，始终存在 0 <= c*g(n) <= f(n)，则咱们能够用 f(n)=Ω(g(n))示意。用图来示意：
Ω只定义下界，只有f(n)不小于c*g(n)，就能够说 f(n)=Ω(g(n))。
比方，对于插入排序，咱们能够说它的工夫复杂度为Ω(n)，不过，这通常没有什么意义，因为插入排序在最好的状况下很少，根本都是在最坏状况或者均匀状况。
ω
ω同样定义的是下界，只不过不蕴含等于，是一种不准确的下界，或者称作松下界（某些书籍翻译为非紧下界）。
用函数来示意：
对于f(n)，存在负数n0、c，使得当 n>n0 时，始终存在 0 <= c*g(n) < f(n)，则咱们能够用 f(n)=ω(g(n))示意。用图来示意：
ω示意仅仅是大Ω去掉等于的状况，其余行为与大Ω截然不同。
艰深了解
| 符号 | 含意 | 艰深了解 |
|---|---|---|
| Θ | 准确的渐近行为 | 相当于“=” |
| O | 上界 | 相当于“<=” |
| o | 松上界 | 相当于“<” |
| Ω | 下界 | 相当于“>=” |
| ω | 松下界 | 相当于“>” |
小结
为了帮忙同学们疾速查阅英文材料，彤哥特地把这几节波及到的英语单词汇总了一下：
| 汉语 | 英文 |
|---|---|
| 复杂度 | complexity |
| 工夫复杂度 | time complexity |
| 空间复杂度 | space complexity |
| 渐近剖析 | asymptotic analysis |
| 最坏状况 | the worst case |
| 最好状况 | the best case |
| 均匀状况 | the average case |
| 准确的渐近行为 | exact asymptotic behavior |
| 低阶项 | low order terms |
| 常数项（前置常数） | leading constants |
| 松上界 | loose upper-bound |
后记
本节，咱们别离从读音、数学、艰深了解等三个方面论述了Θ、O、o、Ω、ω的含意，并在最初给出了这几节波及到的术语对应的英文，有了这些英文，你也能够疾速地查阅这方面的材料。
不过，在咱们平时与人交换的过程中，大家还是习惯于应用大O表示法，一来它示意最坏状况，最坏状况通常能够间接代表算法的复杂度，二来它比拟好书写。
所以，咱们只须要记住大O就能够了，只不过在他人提到Θ、Ω、ω咱们晓得是什么含意就能够了。
后面几节讲了这么多，其实，还是只波及了很简略的算法复杂度。
那么，常见的算法复杂度有哪些呢？
下一节，咱们接着聊。
关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。
发表回复