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

Question

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

Answer 1

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之类的东西。

Answer 2

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

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

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

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