O、Θ、Ω、o、ω,别再傻傻分不清了!
前言
本篇文章收录于专辑: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就可以了,只不过在别人提到Θ、Ω、ω我们知道是什么含义就可以了。
前面几节讲了这么多,其实,还是只涉及了很简单的算法复杂度。
那么,常见的算法复杂度有哪些呢?
下一节,我们接着聊。
关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
阿里云李响荣获 2020 中国开源杰出贡献人物奖,我们找他聊了聊开源和云原生
作者 | 禾易 在第十五届“开源中国开源世界”高峰论坛上,阿里云资深技术专家、etcd 创始人、CNCF TOC 李响荣获 2020 中国开源杰出人物贡献奖。恭喜李响! 去年,全球顶级开源社区云原生计算基金会 CNCF 正式宣布其技术监督委员会席位改选结果。阿里云资深技术专家李响入选,成为该委员会有史以来首张中国面孔。 李响是 CoreOS 最早期的工程师之一,参与创建了 etcd、operator framework、rkt 等开源项目。而在开源社区中,李响作为 etcd 作者被开发者所熟知,etcd 是国际知名且被最为广泛使用的分布式一致性存储系统,被阿里巴巴、腾讯、华为、腾讯、微软、谷歌、VMWare 等企业在生产环境和客户产品中使用,用来解决分布式系统中重要元信息存储、管理和备份的问题,以及分布式系统组件一致性协调的问题。 在加入阿里云后,李响一直在推动云原生领域自动化运维相关理念、Operator 概念、OAM 标准的建立。Operator 给予开发和运维人员在云原生平台构建无状态和复杂应用运维的理论标准和实践基础,大幅度提高了云原生运维平台的覆盖度,在开源生态中涌现出了超过...
- 下一篇
JVM系列之:对象的锁状态和同步
简介 锁和同步是java多线程编程中非常常见的使用场景。为了锁定多线程共享的对象,Java需要提供一定的机制来实现共享对象的锁定,从而保证一次只有一个线程能够作用于共享对象。当第二个线程进入同一个区域的时候,必须等待第一个线程解锁该对象。 JVM是怎么做到的呢?为了实现这个功能,java对象又需要具备什么样的结构呢?快来一起看看吧。 java对象头 Java的锁状态其实可以分为三种,分别是偏向锁,轻量级锁和重量级锁。 在Java HotSpot VM中,每个对象前面都有一个class指针和一个Mark Word。 Mark Word存储了哈希值以及分代年龄和标记位等,通过这些值的变化,JVM可以实现对java对象的不同程度的锁定。 还记得我们之前分享java对象的那张图吗? javaObject对象的对象头大小根据你使用的是32位还是64位的虚拟机的不同,稍有变化。这里我们使用的是64位的虚拟机为例。 Object的对象头,分为两部分,第一部分是Mark Word,用来存储对象的运行时数据比如:hashcode,GC分代年龄,锁状态,持有锁信息,偏向锁的thread ID等等。 在64...
相关文章
文章评论
共有0条评论来说两句吧...