如何向其他人解释什么是大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(f(n)),那么n 个元素的运行时间等于 A F(n) + B(其他时间消耗,比如 CPU 死锁的时间消耗)。理解这些常数a和b的关键是,这些常量a和b是从具体操作中产生的。B基本上代表了操作的“常数开销”,例如,您所做的一些不依赖于集合的大小的预处理。a表示实际项目处理算法的速度。

关键是,你用大O符号来计算某事的规模,所以这些常量并不重要:如果你想弄清楚如何从10到10000个项目,谁在乎不变的开销B?同样,其他关注点肯定会超过乘法常数A的权重。

所以,真正消耗的是 F(n),如果 f 增长一点不像 n,比如 f(n) = 1,你可能会变得非常打——你的运行时间总是 A+B。

如果 f 增长是n倍线性的,比如 f(n)=n,你运行时间将可能根据预期来调整,比如你的用户花费 10 ns 来等待10 个元素,他需要10000 ns 来等待 10000个元素(忽略额外的支出)。但是如果它增长的话很快,就像 n2 ,那你可能会陷入麻烦,他们可能会在你处理一个非常大的集合时增长的非常的快。f(n) = n log(n) 像是一个不错的这种方案,通常情况下,你的操作不可能简单到可以线性增长,但你已经成功的减少了一些东西,这样它的规模就要比 f(n)=n2 好。

实际上,以下是一些很好的例子:

  • O(1):从数组中检索元素。我们知道它在内存中的确切位置,所以我们去拿它。集合是否有10个项或10000项并不重要;它仍然位于索引3,所以我们只需跳转到内存中的位置3。
  • O(n): 从一个链表中提取一个元素。在这里 A= 0.5,因为平局而言,在找到目标元素之前,你必须经过链表的1/2。
  • O(N_2):各种暴力排序算法。因为对于每个元素(N),它们的策略都一样,您将查看所有其他元素n,然后把自己放在正确的位置。
  • O(nlogn):各种“智能”排序算法。事实证明,您只需要查看1010元素集合中的10个元素就可以对自己进行智能排序。大家其他的在集合里。因为其他人都是查看10个元素,并对集合进行适当的编排,这样就足以生成一个排序列表。
  • O(n!):一个“尝试一切”的算法,因为有成比例的算法。n!可能的组合 n 可能解决给定问题的元素。因此,它只是循环遍历所有这样的组合,尝试它们,然后在成功时停止。

热门问答

腾讯云广州一区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开发的,还没有这个接口,因此暂时无法使用

所属标签

扫码关注云+社区