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

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

/ 猿问

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

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

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


查看完整描述

3 回答

?
慕婉清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

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

//img1.sycdn.imooc.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下载
官方微信