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

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

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

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

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

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

这里有一些非常好的答案,但是几乎所有的答案似乎都犯了同样的错误,而且这是一个普遍使用的错误。

非正式的说,我们把 f(n) = O(g(n)),取决于一个缩放因子,并且对于任何一个 n 大于 n0, g(n)大于 f(n)。这意味着 f(n) 增长的不如或在 gn 的边界上。

非正式地,我们写道,f(N)=O(g(N))如果,直到一个标度因子,并且对于所有n大于某个N0,g(N)是更大超过f(N)。即f(N)长得不快比,或者是由上界比g(N)。这并没有告诉我们 f(N) 增长的速度有多快,但保证它不会比g(N)差。

一个具体的例子:n=O(2^n),我们都知道n的增长比2^n慢得多,因此我们可以说它是由上面的指数函数所限制的。n和2^n之间有很大的空间,虽然不是很大的空间,十分紧,但它依旧合理。

为什么我们使用边界而不是一个固定的值呢?主要因为

1。 边界更容易证明

2。 给我们一个更加简短的表达的机会。

如果说我们的算法是O(n.log n) ,意味着在最坏的情况下,n 个输入的运行时间会在 nlogn 到 尽可能大之间波动。

如果相反,我们想说一个函数的增长速度与其他函数一样快,我们将使用 theta 来说明这一点(我会写 T( f(n) ) 来表示 f(n) 的 \Theta)。T( g(n) )是在g(N)上下浮动的,再一次,并且渐近地达到一个标度因子。

即 f(n) = T( g(n) ) <=> f(n) = O(g(n)) 以及 g(N)=O(f(N))。在我们的例子中,我们可以看到n!=T(2^n),因为2^n!=O(N)。

即 和g(N)=O(f(N))。在我们的例子中,我们可以看到n!=T(2^n),因为2^n!=O(N)。!) --这并不是一个严格的限制。

这里还有另一个微妙的维度。当我们使用O(g(N))表示法时,通常我们要讨论的是最坏情况输入,我们要做一个复合语句:在最坏的情况下,运行时间不会比采取g(N)步骤的算法更糟糕。同样地,模缩放和足够大的n。但有时我们想要讨论的运行时间平均甚至最佳的情况。

Vanilla quicksort是一个很好的例子,像其他一样。在最坏的情况下是T(n ^ 2)(这实际上至少需要N ^ 2步,但不明显),但T(n.log N)在一般情况下,预期数量的步骤是n.log n,最好的情况下也是T(n.log N)- 但你可以改进它的,例如,检查这种情况下阵列是否已经有序,最好的情况下的运行时间排序将T(n)。

这与你关于这些界限的实际实现的问题有什么关系?不幸的是,O()表示法隐藏了实际实现必须处理的常量。因此,虽然我们可以说,例如,对于一个T(n^2)运算,我们必须访问每一对可能的元素,但是我们不知道我们要访问它们多少次(除非它不是n的函数)。所以我们可以每对访问10次,或者10^10次,而T(n^2)语句没有区别。低阶函数也是隐藏的-我们可以访问每一对元素一次,每个单独的元素访问100次,因为n^2+100 N=T(n^2)。O()表示法的思想是,对于足够大的n,这一点都不重要,因为n^2比100 N大得多,以至于我们甚至没有注意到100 N对运行时间的影响。然而,我们经常处理“足够小”的问题,常数等因素会产生真正的、显著的差异。

例如,快速排序(平均成本T(n.log n)))和堆排序(平均成本T(n.log )。这两种排序算法的平均成本都是相同的,但是快速排序通常比堆排序快得多。这是因为堆排序在每个元素上做的比较比快速排序要多一些。

这并不是说O()表示法是无用的,只是不精确。对于小的n来说,这是一个相当迟钝的工具。

(作为本论文的最后一个说明,请记住,O()表示法只描述了任何函数的增长---它不一定是时间,它可能是内存、分布式系统中交换的消息或并行算法所需的CPU数量)。

热门问答

腾讯云广州一区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万条可申请配置。未配置专属上行码号用户可先下发短信后用户回复。感谢您对腾讯云短信的支持。

所属标签

扫码关注云+社区