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

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

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

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

比如,在某个数据结构上,一个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%的时间,线性时间意味着每次查看一次输入。

热门问答

腾讯云广州一区DNS变更,需要怎么操作?

思潮澎湃轻描淡写的生活,但思潮澎湃
推荐
我也收到相关的通知了,这里分享下~ 2019年1月31日,腾讯云将对广州地区旧的基础网络DNS服务器(10.225.30.181、10.225.30.223)进行下线。在此期间,腾讯云提供最新的DNS服务器供您更新使用。 我们建议您尽快将DNS服务器配置进行更新,并且我们为您提供...... 展开详请

CMQ创建队列成功,紧接着发送消息,报队列不存在?

CreateQueue成功后,创建队列的时间为1s,您可以等待下在sendMessage

云呼叫中心只能用户自己开发吗?

腾讯云通信团队

腾讯 · 腾讯云通信团队 (已认证)

腾讯高级产品经理
推荐

目前呼叫中心只有API文档,需要用户自己开发。如果用户需要saas系统的呼叫中心可以使用智能外呼机器人:https://cloud.tencent.com/product/ccsr

ios端推流setRenderRotation无效?

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐

你有没有调整观众端表现,即通过对 LivePushConfig 中的homeOrientation设置项进行配置,它控制的是观众端看到的视频宽高比是16:9还是6:19,调整后的结果可以用播放器查看以确认是否符合预期。

腾讯云直播 CNAME 记录添加 的 值是多少???

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐
第一步:域名备案 控制台进行域名提交管理前,需对域名进行备案,详情请查看 域名备案 和 域名备案和配置常见问题 文档。 第二步:添加域名 在视频直播菜单栏内选择【域名管理】,在域名管理页面可以看到已创建域名、类型、状态、添加时间和操作。 可添加和管理的域名类型有播放域名和推流域...... 展开详请

【建议】【API】使用API创建子网的时候允许指定已有路由表?

推荐

控制台使用的是新的接口,批量创建子网,https://cloud.tencent.com/document/product/215/31960,可以指定路由表。terraform开发的时候是基于api2.0开发的,还没有这个接口,因此暂时无法使用

所属标签

扫码关注云+社区