如何向其他人解释什么是大O阶?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (10)
  • 关注 (0)
  • 查看 (106)

我想问一下这对于我的代码意味着什么?我理解他的数学含义,但是我无法理解在概念上什么意思。

比如,在某个数据结构上,一个O(1)的操作,我认为他执行的操作的数量不会增加。一个 O(n)的操作意味着你需要对每个元素执行一组操作。有人能解答我的下面几个问题么?

  • O (n^2) 的操作是什么?
  • 如果一个操作是 O(n Log(N)),这意味着什么?
  • 什么样的人才能写出 O(x!) 的算法
提问于
用户回答回答于

为了实用起见,唯一重要的O()是:

  • O(1)“恒定时间”-所需时间与输入的大小无关。作为一个粗略的分类,我将在这里包含哈希查找和UNION-find等算法,尽管它们实际上都不是O(1)。
  • O(log(N))“对数”--随着输入的增加,它会变慢,但是一旦输入变得相当大,它就不会有足够的变化来担心。如果您的运行时对合理大小的数据没有问题,那么您可以随心所欲地使用更多的额外数据,而且它仍然会很好。
  • O(N)“线性”-输入越多,花费的时间就越长,在一个均衡的权衡中。三倍的输入大小将花费大约三倍的时间。
  • O(n log(N))“好于二次”--增加输入大小会造成一些问题,但它仍然是可控的。这个算法可能很不错,只是与那些可以在线性时间内解决的问题相比,根本的问题更难解决(对于输入数据的决策不那么聪明化)。如果您的输入大小正在上升,不要假设您可以在不改变架构的情况下处理两倍的大小。不过,如果输入的大小增加了一点,也没关系;只需注意倍数即可。
  • O(n^2)“二次型”-它实际上只会达到你输入的某一大小,所以请注意它能得到多大。而且,你的算法可能很烂--仔细想想有没有O(n log(N))算法能满足你的需要。一旦你来到这里,你会对我们所拥有的神奇的硬件感到非常感激。不久的过去,因为实际情况,你试图做的事情是不可能的。
  • O(n^3)“立方”--与O(n^2)没有质的区别。同样的问题也适用,只是更多。更聪明的算法很有可能会把这一次分配到更小的地方,比如O(n^2 log(N))或O(n^2.8...),但同样,这很有可能不值得麻烦。(您的实际输入大小已经受到限制,因此,对于更聪明的算法来说,可能需要的常数因素可能会淹没它们在实际情况下的优势。而且,思考是缓慢的;让电脑细细地思考它可能会节省你的时间。)
  • O(2^n) "指数" - 这个问题有点大,除非你是个白痴。这个算法的输入上线有一个特定的值,你很快就能知道自己是不是到了这个限制。

就是这样。在这些(甚至大于 2^n )之间还有许多其他的可能的算法,但它们在实践中并不经常发生,它们与这些中的一个也没有本质上的区别。立方算法已经有一点伸缩性,我只包括它们,因为我经常碰到它们,是值得一提的算法(如矩阵乘法)。

这类算法到底发生了什么?嗯,我认为你有一个良好的开端,虽然有许多例子不符合这些特点。但对于上述情况,我认为通常情况如下:

  • O(1)-你最多只看一段固定大小的输入数据,可能没有。示例:排序列表的最大值。
    • 或者输入大小是有界的。示例:添加两个数字。(注意n个数的增加是线性时间。)
  • O(Logn)-输入的每个元素都告诉您足够多的信息来忽略大部分的输入。示例:当您在二进制搜索中查看数组元素时,它的值告诉您,您可以忽略数组的“一半”,而无需查看其中的任何一个。或者类似地,您所查看的元素为您提供了足够多的剩余输入的摘要,您不需要查看它。
    • 但是,一般没有什么特别之处--如果你在每一步都能忽略10%的输入,它仍然是对数的。
  • O(n) -每个输入元素执行一定数量的工作。(但见下文)。
  • O(n log(N))-有几个变体。
    • 你可以把输入分成两个部分(不超过线性时间),独立解决每个部分上的问题,然后把两个部分结合起来形成最终的解决方案。两部分的独立性是关键。例如:经典的递归归并排序。
    • 每一次线性时间传递数据,你就可以找到你的解决方案。示例:如果考虑到每个元素在每个分区步骤的最终排序位置的最大距离(是的,我知道实际上是O(n^2),因为有退化的枢轴选择。但实际上,它属于我的O(n log(N))范畴。
  • O(n^2)-你必须查看每一对输入元素。
    • 或者你不知道,但你认为你知道,而且你使用了错误的算法。
  • O(n^3)-嗯...我对这些没有什么夸张的描述。可能是:
    • 您正在查看每一对输入,但您所做的操作需要再次查看所有的输入
    • 输入的整个图结构是相关的。
  • O(2^n)-您需要考虑输入的每个可能的子集。

这些都不严谨。尤其是线性时间算法(O(n)):想想你要看看所有的输入实例,然后他们中的一半,那一半的人,等待或其他方式--你叠在一起的双输入,然后递归的输出。这些不符合上面的描述,因为你不会每次都看一次,但它仍然是线性时间。然而,99.2%的时间,线性时间意味着每次查看一次输入。

热门问答

对象存储COS有没有日志功能?

Hyman Wang

腾讯云 · 高级产品经理 (已认证)

负责腾讯云游戏行业产品规划及发展。关注游戏行业生态,致力于腾讯内部游戏生态和技术能力开放,以及周边游戏生态资源整合。
推荐已采纳

你的cos 是否开通了 CDN 加速,如果开通了CDN 加速,可以去 CDN 的控制台下: (统计分析 --- 监控 )页面下拉到底部,可以通过 URL 查看流量情况。

对象存储里的视频能在线播放么?

Jinqn

腾讯 · 高级工程师 (已认证)

腾讯云COS前端开发
推荐

购买的云数据库里面有什么类型的数据库?有SQLserver吗?可以自己安装SQLserver吗?

帅的惊动我国计算机大神
推荐已采纳
云关系型数据库让您在云中轻松部署、管理和扩展的关系型数据库,提供安全可靠、伸缩灵活的按需云数据库服务。腾讯云关系型数据库提供 MySQL、SQL Server、MariaDB、PostgreSQL 数据库引擎,并针对数据库引擎的性能进行了优化。云关系型数据库是一种高度可用的托管服...... 展开详请

linux如何限制单一ip对服务器的日访问量?

小爱同学

腾讯云 · 技术支持 (已认证)

推荐
您根据当前网站规模和业务了解下【网站管家 WAF】,企业站点可有效抵御恶意攻击,垃圾访问。 图片.png 您反馈网站短信验证码被盗刷,也可结合自己业务,可自行部署iptables进行手动拦截。或其他方式 例如您的网站是nginx,在web配置文件中开启配置HttpLimitR...... 展开详请

兼容性测试只能上传apk测试的吗?

WeTest质量开放平台团队专注游戏,提升品质
推荐

目前不支持公众号的兼容测试,还请知晓

关于群自动解散的问题?

安稳

腾讯科技 · 工单技术支持 (已认证)

推荐
您好,临时群是没有的。云通信的群组只有私有群(Private)、公开群(Public)、聊天室(ChatRoom)、音视频聊天室(AVChatRoom)和在线成员广播大群(BChatRoom)这五种。 您说的这个需求,思路:创建群组时,服务端记录一下时间,到达约定解散的时间以后,...... 展开详请

所属标签

扫码关注云+社区