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

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

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

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

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

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

The big thing that Big-O notation means to your code is how it will scale when you double the amount of "things" it operates on. Here's a concrete example:

大O阶意味着你的代码如何缩放你的问题的规模,这里有一些例子。

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

因为快排是 O(n log(n)) 阶,而冒泡排序是 O(n^2) 阶的,当排序10个物体时,快排比冒泡排序快了3倍。当排序100个物体时,是14倍。显然,挑选最快的算法是很重要的。当你拥有百万行的数据库时,它可能意味着你的查询在0.2秒内执行,而不是占用大量时间。

另一件要考虑的事情是,糟糕的算法是摩尔定律无法提供帮助的一件事。例如,如果你有一些科学计算是O(n^3),它每天可以计算100件事,双倍的处理器速度只会在一天内得到125件事。但是,把这个计算敲到O(n^2),你每天要做1000件事。

补充:其实,大0不讨论性能比较不同算法在同一特定大小的点,而是比较性能相同的算法在不同大小的点:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

热门问答

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

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

快照容量与费用的比例?如何关闭停用?

帅的惊动我国计算机大神
推荐已采纳
快照已于2019年1月22日0时启动正式商业化进程,商业化后所有存量快照和新产生的快照将根据快照使用的存储容量进行收费。 在快照商业化后,腾讯云仍旧会在国内主要地域为用户提供一定量的免费额度。免费额度策略如下: 免费额度覆盖范围为中国大陆地域,中国香港及海外地域暂无免费快照额...... 展开详请

云服务器购买后多久生效能使用?

Eli Qiao

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

腾讯云CVM后台高级研发工程师
推荐

如果使用公有镜像,一般 10s 左右后台就可以创建完成。

欠费资源销毁怎么解决?

西风

renzha.net · 站长 (已认证)

www.renzha.net
推荐
当您的账户发生欠费时,对象存储 COS 会在24小时后停止服务,您的数据可以继续保留120天,如果在此期间未进行续费使账户余额大于等于0, 您的数据将会被销毁。 注意: 欠费停服后,数据占用的存储容量会持续计费,直到销毁数据。 销毁数据后,不可恢复。 用户续费使账户余额大于等于...... 展开详请

React项目的try_files机制,在COS上怎么配置?

galenye

腾讯 · 工程师 (已认证)

对象存储专业搬砖工
推荐
COS的静态网站可以设置默认索引,你这里应该是想实现react-router spa场景下刷新浏览器时,不希望报404的场景吧 可以在COS静态网站这设置一个错误文档的默认索引来实现类似try_files的功能 image.png ... 展开详请

用户主动向云服务器的号码发送短信(不是回复),该条消息能否回调给业务服务器?

推荐

您好,主动上行需配置专属上行码号,月发送量大于300万条可申请配置。未配置专属上行码号用户可先下发短信后用户回复。感谢您对腾讯云短信的支持。

所属标签

扫码关注云+社区