如何向其他人解释什么是大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(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 可能解决给定问题的元素。因此,它只是循环遍历所有这样的组合,尝试它们,然后在成功时停止。

热门问答

对象存储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)这五种。 您说的这个需求,思路:创建群组时,服务端记录一下时间,到达约定解散的时间以后,...... 展开详请

所属标签

扫码关注云+社区