O、Θ、Ω、o、ω，别再傻傻分不清了！

我不是女神ヾ 2023-03-01 10:11 4阅读 0赞

![file][]

# 前言 #

> 本篇文章收录于专辑：[http://dwz.win/HjK][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))表示。

用图来表示：

![file][file 1]

Θ同时定义了上界和下界，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\*n2，当然，你说g(n)是2\*n2也没问题，所以，g(n)实际上满足这个条件的一组函数。

好了，如果Θ你能理解了，下面四个就好理解了。

## O ##

O定义了算法的上界。

用函数来表示：

对于f(n)，存在正数n0、c，使得当 n>=n0 时，始终存在 0 <= f(n) <= c*g(n)，则我们可以用 f(n)=O(g(n))表示。

用图来表示：

![file][file 2]

O只定义上界，只要f(n)不大于c\*g(n)，就可以说 f(n)=O(g(n))。

比如说，对于插入排序，我们说它的时间复杂度是O(n^2)，但是，如果用Θ来表示，则必须分成两条：

1.  最坏的情况下，它的时间复杂度为Θ(n^2)；
2.  最好的情况下，它的时间复杂度为Θ(n)。

这里的n2只是g(n)这一组函数中最小的上界，当然，g(n)也可以等于n3。

不过，我们一般说复杂度都是指的最小的上界，比如，这里插入排序的时间复杂度如果说是O(n^3)，从理论上来说，也没问题，只是不符合约定罢了。

> 插入排序最好的情况就是数组本身就是有序的。

## o ##

o定义的也是算法的上界，不过它不包含等于，是一种不精确的上界，或者称作松上界（某些书籍翻译为非紧上界）。

用函数来表示：

对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < c*g(n)，则我们可以用 f(n)=o(g(n))表示。

用图来表示：

![file][file 3]

o表示仅仅是大O去掉等于的情况，其他行为与大O一模一样。

## Ω ##

Ω定义了算法的下界，与O正好相反。

用函数来表示：

对于f(n)，存在正数n0、c，使得当 n>=n0 时，始终存在 0 <= c*g(n) <= f(n)，则我们可以用 f(n)=Ω(g(n))表示。

用图来表示：

![file][file 4]

Ω只定义下界，只要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))表示。

用图来表示：

![file][file 5]

ω表示仅仅是大Ω去掉等于的情况，其他行为与大Ω一模一样。

# 通俗理解 #

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th>含义</th> 
   <th>通俗理解</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Θ</td> 
   <td>精确的渐近行为</td> 
   <td>相当于“=”</td> 
  </tr> 
  <tr> 
   <td>O</td> 
   <td>上界</td> 
   <td>相当于“&lt;=”</td> 
  </tr> 
  <tr> 
   <td>o</td> 
   <td>松上界</td> 
   <td>相当于“&lt;”</td> 
  </tr> 
  <tr> 
   <td>Ω</td> 
   <td>下界</td> 
   <td>相当于“&gt;=”</td> 
  </tr> 
  <tr> 
   <td>ω</td> 
   <td>松下界</td> 
   <td>相当于“&gt;”</td> 
  </tr> 
 </tbody> 
</table>

# 小结 #

为了帮助同学们快速查阅英文资料，彤哥特地把这几节涉及到的英语单词汇总了一下：

<table> 
 <thead> 
  <tr> 
   <th>汉语</th> 
   <th>英文</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>复杂度</td> 
   <td>complexity</td> 
  </tr> 
  <tr> 
   <td>时间复杂度</td> 
   <td>time complexity</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>space complexity</td> 
  </tr> 
  <tr> 
   <td>渐近分析</td> 
   <td>asymptotic analysis</td> 
  </tr> 
  <tr> 
   <td>最坏情况</td> 
   <td>the worst case</td> 
  </tr> 
  <tr> 
   <td>最好情况</td> 
   <td>the best case</td> 
  </tr> 
  <tr> 
   <td>平均情况</td> 
   <td>the average case</td> 
  </tr> 
  <tr> 
   <td>精确的渐近行为</td> 
   <td>exact asymptotic behavior</td> 
  </tr> 
  <tr> 
   <td>低阶项</td> 
   <td>low order terms</td> 
  </tr> 
  <tr> 
   <td>常数项（前置常数）</td> 
   <td>leading constants</td> 
  </tr> 
  <tr> 
   <td>松上界</td> 
   <td>loose upper-bound</td> 
  </tr> 
 </tbody> 
</table>

# 后记 #

本节，我们分别从读音、数学、通俗理解等三个方面阐述了Θ、O、o、Ω、ω的含义，并在最后给出了这几节涉及到的术语对应的英文，有了这些英文，你也可以快速地查阅这方面的资料。

不过，在我们平时与人交流的过程中，大家还是习惯于使用大O表示法，一来它表示最坏情况，最坏情况通常可以直接代表算法的复杂度，二来它比较好书写。

所以，我们只需要记住大O就可以了，只不过在别人提到Θ、Ω、ω我们知道是什么含义就可以了。

前面几节讲了这么多，其实，还是只涉及了很简单的算法复杂度。

那么，常见的算法复杂度有哪些呢？

下一节，我们接着聊。

> 关注公号主“彤哥读源码”，解锁更多源码、基础、架构知识。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbmd0b25nMQ_size_16_color_FFFFFF_t_70]

[file]: /images/20230209/141a86084ba14704a8c919660536f691.png
[http_dwz.win_HjK]: http://dwz.win/HjK
[file 1]: /images/20230209/c5adc7541e274c94a9bfc796a7188284.png
[file 2]: /images/20230209/c0f2200f1c094577ac36f82dae8c5385.png
[file 3]: /images/20230209/7fcfbd9d088e4dabb025a191e9b6837f.png
[file 4]: /images/20230209/7a76c213296341b3826b59096b935c03.png
[file 5]: /images/20230209/0c137252a2a44c16826605aa7d967832.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbmd0b25nMQ_size_16_color_FFFFFF_t_70]: /images/20230209/e086a8887aef43be83c6e642d3eb9c54.png