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

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

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

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

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

热门问答

域名注册时写了企业,可以转为个人的吗?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
可以的,操作如下 登录控制台 登录 腾讯云控制台。 选择 “云产品 > 域名与网站 > 域名注册”,进入 “域名服务” 页面,查看已购买的所有域名信息。 修改/过户域名信息 在需要修改域名信息的域名行中,单击【更多】,选择【域名信息修改】。如下图所示: 也可直接单击需要修改域名信...... 展开详请

如何按照上传时间顺序,获取cos bucket 中的object信息?

波斯狗儿对象存储产品经理
推荐
对象存储是 KV 有序存储,只能按对象键 UTF-8 字符顺序排。详细了解对象的概念:https://cloud.tencent.com/document/product/436/13324 如果需要按时间列表,需要在上传时就指定好路径,这样列表的时候也是按顺序的。比如 pho...... 展开详请

云开发环境和开发者自己的服务器能连通吗?

李成熙heyli

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

腾讯高级工程师,专注于工程化及性能优化。 https://github.com/lcxfs1991
可以的请参考这份教程: https://github.com/TencentCloudBase/mp-book/blob/master/guide/readme.md#3-%E5%9C%A8%E8%87%AA%E5%B7%B1%E7%9A%84%E6%9C%8D%E5%8A%A1...... 展开详请

腾讯云 COS 怎么才能外链调用 m3u8 到别的网站播放?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
设置公有读私有写:当访问对象时,COS 读取到对象的权限为公有读,此时无论存储桶为何种权限,对象都可以被直接下载 设置步骤 登录 对象存储控制台,选择左侧菜单栏【存储桶列表】,进入存储桶列表页面。单击需要修改对象权限的对应存储桶,进入存储桶。 📷 找到需要设置权限的对象(如 e...... 展开详请

云通信IM 可以发送语音消息吗?

应兆康腾讯云+校园合伙人
可以的哦,在云通信IM的文档中有写 消息类型(文本,图片,语音,表情等自定义消息): 文本:最大 1~2k 字节(支持透传特殊字符); 图片:原图/缩略图/大图(支持格式:png/gif/jpeg/jpg/webp); 语音:异步语音消息(语音支持暂无上限); 表情等自定义消息...... 展开详请

Ubuntu搭建的WordPress如何修改php.ini?

滑稽园扛把子

Swoole · PHP开发工程师 (已认证)

As a PHP Developer
推荐
php新手很多不知道怎么查配置文件在哪,这里提供一个很简单的方法 使用 php -i 命令可以打印php的详细信息,可以把这堆东西输出一下 php -i > outputphp.txt,结合 grep 查找命令 php -i| grep php.ini 打印结果如下 Config...... 展开详请

所属标签

扫码关注云+社区