omega是什么意思（听说我很穷）

大财经2023-03-21 10:05:330阅

本篇文章收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的知识。

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

下一节，我们接着聊。

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

符号含义通俗理解Θ精确的渐近行为相当于“=”O上界相当于“<=”o松上界相当于“<”Ω下界相当于“>=”ω松下界相当于“>”

比如，对于插入排序，我们可以说它的时间复杂度为Ω(n)，不过，这通常没有什么意义，因为插入排序在最好的情况下很少，基本都是在最坏情况或者平均情况。

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

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

ΘΘ定义了一种精确的渐近行为（exact asymptotic behavior），怎么说呢？

ωω同样定义的是下界，只不过不包含等于，是一种不精确的下界，或者称作松下界（某些书籍翻译为非紧下界）。

汉语英文复杂度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

本节，我们就来解决这个问题。

用图来表示：

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

O，/??/，大Oho，/??/，小ohΘ，/?θi?t?/，thetaΩ，/o??meɡ?/，大Omegaω，/o??meɡ?/，小omega是不是跟老师教得不太一样^^

用函数来表示：

OO定义了算法的上界。

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

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

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

那么，这些符号又是什么意思呢？

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

我们先来纠正一波读音：

用图来表示：

比如说，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)实际上满足这个条件的一组函数。

Ω只定义下界，只要f(n)不小于c*g(n)，就可以说 f(n)=Ω(g(n))。

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

用函数来表示：

用图来表示：

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

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

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

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

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

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

用函数来表示：

Θ同时定义了上界和下界，f(n)位于上界和下界之间，且包含等号。