Big-O和Little-O表示法之间的区别
Jef*_*ott 301 algorithm big-o time-complexity asymptotic-complexity little-o
Big-O表示法O(n)和Little-O表示法有o(n)什么区别？
Tyl*_*nry 411
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 <)
- 是 - 区别在于两个函数是否渐近相同.直观地,我喜欢想到大O意味着"增长不快"(即以相同速率或更慢速度增长)和小o意味着"增长严格慢于". (134认同)
- 将其复制到维基百科？这比那里的要好得多. (8认同)
- @Phil好的措辞.我把它解决了. (5认同)
- 请注意“在 Little-o 中，必须存在一个最小 x，在此之后，无论 k 有多小，只要它不是负数或零，不等式都成立。” 它不是“对于每个‘a’，都有一个‘k’：......”，而是“对于每个‘k’，有一个‘a’：......” (2认同)
- “在 Little-o 中，必须存在一个最小 x，在此之后，无论 k 有多小，只要它不是负数或零，不等式都成立。” 不，这是不正确的。 (2认同)
Cra*_*ney 184
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
这是一张表,显示了一般的想法:
(注意:该表是一个很好的指南,但它的限制定义应该是上限而不是正常限制.例如,3 + (n mod 2) 永远在3到4之间振荡.O(1)尽管没有正常的限制,它仍然存在,因为它仍然有a lim sup:4.)
我建议记住Big-O符号如何转换为渐近比较.比较更容易记住,但不太灵活,因为你不能说n O(1) = P之类的东西.
- 哦,我明白了.大欧米茄为lim> 0,Big Oh为lim <infinity,Big Theta为两个条件时,意味着0 <lim <无穷大. (3认同)
ago*_*nst 40
我发现当我无法在概念上掌握某些东西时,思考为什么会使用X有助于理解X.(不是说你没有尝试过,我只是在设置舞台.)
[你知道的东西]分类算法的常用方法是运行时,通过引用算法的大复杂性,你可以很好地估计哪一个是"更好" - 无论哪个具有"最小"功能在O!即使在现实世界中,O(N)比O(N²)"更好",除非像超大质量常数之类的傻事.[/你知道的东西]
假设有一些在O(N)中运行的算法.很好,对吧？但是,让我们说你(你很聪明的人,你)想出一个在O(N/loglogloglogN)中运行的算法.好极了!它更快!但是当你撰写论文时,你会一遍又一遍地写下傻傻的写作.所以你写了一次,然后你可以说"在本文中,我已经证明了算法X,以前可以在时间O(N)中计算,实际上是在o(n)中可计算的."
因此,每个人都知道你的算法更快 - 有多少不清楚,但他们知道它更快.理论上.:)
cgl*_*cet 12
一般来说
\n渐近符号你可以理解为：缩小时函数如何比较？（测试这一点的一个好方法就是使用像Desmos这样的工具并使用鼠标滚轮）。尤其：
\n- \n
f(n) \xe2\x88\x88 o(n)意思是：在某个时刻，你越缩小，就越f(n)会被主导n（它将逐渐偏离它）。 \ng(n) \xe2\x88\x88 \xce\x98(n)意味着：在某些时候，缩小不会改变g(n)比较方式n（如果我们从轴上删除刻度，您将无法分辨缩放级别）。 \n
最后h(n) \xe2\x88\x88 O(n)意味着函数h可以属于这两个类别中的任何一个。它可以看起来很像，也可以比增加时n越来越小。基本上， 和也都在.nnf(n)g(n)O(n)
我认为这个维恩图（改编自本课程）可以帮助：
\n
这与我们用于比较数字的方法完全相同：
\n
在计算机科学领域
\n在计算机科学中，人们通常会证明给定的算法同时存在上限O和下限。当两个界限满足时，意味着我们找到了解决该特定问题的渐近最优算法\xce\x98。
例如，如果我们证明一个算法的复杂度为O(n)，则(n)意味着它的复杂度为\xce\x98(n)。（这就是 的定义\xce\x98，它或多或少地翻译为“渐近相等”。）这也意味着没有算法可以解决 中的给定问题o(n)。再次粗略地说“这个问题不能（严格）少于n步骤解决”。
通常o在下界证明中使用 来显示矛盾。例如：
\n\n假设算法可以逐步找到大小数组中
\nA的最小值。因为它无法看到输入中的所有项目。换句话说，至少有一件物品从未见过。算法无法区分两个相似输入实例之间的差异，其中只有值发生变化。如果是这些实例之一中的最小值，而另一个实例中不是最小值，则将无法在（至少）这些实例之一中找到最小值。换句话说，找到数组中的最小值是（没有算法可以解决这个问题）。no(n)A \xe2\x88\x88 o(n)xAAxxA(n)o(n)
有关下限/上限含义的详细信息
\n的上限O(n)仅意味着即使在最坏的情况下，算法也将在最多n步骤中终止（忽略所有常数因子，包括乘法和加法）。的下界(n)是关于问题本身的陈述，它表示我们构建了一些示例，其中给定的问题无法通过任何算法在少于n步骤的时间内解决（忽略乘法和加法常数）。步骤数最多n和最少，n所以这个问题的复杂度是“恰好n”。而不是每次我们只写\xce\x98(n)简短的内容时都说“忽略常数乘法/加法因子”。