专栏首页彤哥读源码O、Θ、Ω、o、ω,别再傻傻分不清了!

O、Θ、Ω、o、ω,别再傻傻分不清了!

关注公众号“彤哥读源码”,解锁更多源码、基础、架构知识!

前言

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

前面几节,我们一起学习了算法的复杂度如何分析,并从最坏、平均、最好以及不能使用最坏情况全方位无死角的剖析了算法的复杂度,在我们表示复杂度的时候,通常使用大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),但是,如果用Θ来表示,则必须分成两条:

  1. 最坏的情况下,它的时间复杂度为Θ(n^2);
  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就可以了,只不过在别人提到Θ、Ω、ω我们知道是什么含义就可以了。

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

那么,常见的算法复杂度有哪些呢?

下一节,我们接着聊。

本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01),作者:丹卿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 什么情况下不能使用最坏情况评估算法的复杂度?

    上一节,我们从最坏、平均、最好三种情况分析了算法的复杂度,得出结论,通常来说,使用最坏情况来评估算法的复杂度完全够用了。

    彤哥
  • 复杂度分析的套路及常见的复杂度

    上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大O来表示算法的复杂度,不仅合理,而且书写方便。

    彤哥
  • 死磕 java线程系列之线程池深入解析——定时任务执行流程

    前面我们一起学习了普通任务、未来任务的执行流程,今天我们再来学习一种新的任务——定时任务。

    彤哥
  • 2019二级C题库及解析(7)

    此题为if...else...语句的嵌套,第二if...else...作为第一个if...else...语句else部分的复合语句。

    用户6755376
  • TCP/IP之DHCP协议静态配置DHCP协议

    有两种获取方法,一种是静态配置,就是从网络管理员获取一个给定的IP地址,也叫硬编码,还有一种就是动态配置IP地址,这就是我们即将要讲的DHCP协议,动态主机配置...

    desperate633
  • 【数据库】MySQL经典面试题(练习)

    【数据库】MySQL经典面试题(练习) 一、删除除了学号字段以外,其它字段都相同的冗余记录,只保留一条!(也就是要删除凤姐和田七中一条重复数据只留一条) ?...

    Java帮帮
  • 一级指针简单理解

    在 C 中操作地址就可以操作值,就跟 java 中两个引用类型拿到引用可以操作内一个对象一样。

    潇洒
  • SCF与自然语言处理为你的网站赋能

    自然语言的内容有很多,今天本文所介绍的自然语言处理部分是“文本摘要”和“关键词提取”,很多朋友都应该有自己的博客,在做博客的时候,经常会发一些文章,这些文章发出...

    Dfounderliu
  • iOS开发之再探多线程编程:Grand Central Dispatch详解

    Swift3.0相关代码已在github上更新。之前关于iOS开发多线程的内容发布过一篇博客,其中介绍了NSThread、操作队列以及GCD,介绍的不够深入。今...

    lizelu
  • 企业服务,赛道决定路径

    企业服务这个话题,在 15 年被炒热之后,不温不火了好几年,最近又被时常提起,关键词都是“难做”。

    CODING研发管理系统

扫码关注云+社区

领取腾讯云代金券