为了账号安全,请及时绑定邮箱和手机立即绑定

Big-O和Little-O表示法之间的区别

/ 猿问

Big-O和Little-O表示法之间的区别

呼如林 2019-09-18 10:34:16

Big-O表示法O(n)和Little-O表示法有o(n)什么区别?


查看完整描述

3 回答

?
慕田峪7331174

f∈O(g)基本上说


对于常数k > 0的至少一个选择,你可以找到一个常数a,使得不等式0 <= f(x)<= kg(x)适用于所有x> a。


注意,O(g)是该条件所适用的所有函数的集合。


f∈o(g)基本上说


对于常数k > 0的每个选择,你可以找到一个常数a,使得不等式0 <= f(x)<kg(x)适用于所有x> a。


再次注意o(g)是一组。


在Big-O中,只需要找到一个特定的乘数k,其中不等式保持超过某个最小x。


在Little-o中,必须存在一个最小x,在此之后,不管你做出多小的k,不等式都会成立,只要它不是负数或零。


这两个都描述了上限,虽然有点违反直觉,Little-o是更强的说法。如果f∈o(g),则f和g的增长率之间存在比f∈O(g)更大的差距。


差异的一个例子是:f∈O(f)为真,但f∈o(f)为假。因此,Big-O可以被解读为“f∈O(g)意味着f的渐近增长不比g更快”,而“f∈o(g)意味着f的渐近增长严格地慢于g”。这就像<=对抗<。


更具体地,如果g(x)的值是f(x)的值的常数倍,则f∈O(g)为真。这就是为什么在使用big-O表示法时可以删除常量的原因。


然而,对于f∈o(g)为真,则g必须在其公式中包括更高的x次幂,因此当x变大时,f(x)和g(x)之间的相对间隔实际上必须变大。


要使用纯数学示例(而不是参考算法):


对于Big-O,以下情况属实,但如果使用little-o则不然:


x²∈O(x²)

x²∈O(x²+ x)

x²∈O(200 *x²)

对于little-o,以下情况属实:


x²∈o(x³)

x²∈o(x!)

ln(x)∈o(x)

注意,如果f∈o(g),这意味着f∈O(g)。例如x²∈o(x³)所以x²∈O(x³)也是如此,(再次认为O as <=和o as <)


查看完整回答
反对 回复 2019-09-18
?
慕婉清6462132

Big-O对于小o 来说就是如此<。Big-O是包含上限,而little-o是严格的上限。

例如,函数f(n) = 3n是:

  • O(n²)o(n²)O(n)

  • 不是O(lg n)o(lg n)o(n)

类似地,数字1是:

  • ≤ 2< 2≤ 1

  • 不是≤ 0< 0< 1

这是一张表,显示了一般的想法:

//img.mukewang.com/5d8197e200011b0c04980298.jpg

(注意:该表是一个很好的指南,但它的限制定义应该是上限而不是正常限制。例如,3 + (n mod 2) 永远在3到4之间振荡。O(1)尽管没有正常的限制,它仍然存在,因为它仍然有a lim sup:4.)

我建议记住Big-O符号如何转换为渐近比较。比较更容易记住,但不太灵活,因为你不能说n O(1) = P之类的东西。


查看完整回答
反对 回复 2019-09-18
?
互换的青春

我发现当我无法在概念上掌握某些东西时,思考为什么要使用X有助于理解X.(不是说你没有尝试过,我只是在设置舞台。)

[你知道的东西]分类算法的常用方法是运行时,通过引用算法的大复杂性,你可以很好地估计哪一个是“更好” - 无论哪个具有“最小”功能在O!即使在现实世界中,O(N)比O(N²)“更好”,除非像超大质量常数之类的傻事。[/你知道的东西]

假设有一些在O(N)中运行的算法。很好,对吧?但是,让我们说你(你很聪明的人,你)想出一个在O(N / loglogloglogN)中运行的算法。好极了!它更快!但是当你撰写论文时,你会一遍又一遍地写下傻傻的写作。所以你写了一次,然后你可以说“在本文中,我已经证明了算法X,以前可以在时间O(N)中计算,实际上是在o(n)中可计算的。”

因此,每个人都知道你的算法更快 - 有多少不清楚,但他们知道它更快。理论上。:)


查看完整回答
反对 回复 2019-09-18

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信