大 O 和小 O 表示法的区别
Big-O 表示法 O(n) 和 Little-O 表示法 o(n) 之间有什么区别？
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
f ∈ O(g) 本质上说
请注意，O(g) 是满足此条件的所有函数的集合。
f ∈ o(g) 本质上说
再次注意 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) 为真。这就是为什么在使用大 O 表示法时可以删除常量。
然而，要使 f ∈ o(g) 为真，则 g 的公式中必须包含 x 的更高幂，因此 f(x) 和 g(x) 之间的相对分离实际上必须随着 x 变大而变大。
使用纯粹的数学示例（而不是参考算法）：
以下对于 Big-O 来说是正确的，但如果您使用little-o，则不是这样：
以下对于小 o 成立：
请注意，如果 f ∈ o(g)，这意味着 f ε O(g)。例如 x² ∈ o(x³) 因此 x² ∈ O(x³) 也是正确的（再次将 O 视为
<=并将 o 视为<）f ∈ O(g) says, essentially
Note that O(g) is the set of all functions for which this condition holds.
f ∈ o(g) says, essentially
Once again, note that o(g) is a set.
In Big-O, it is only necessary that you find a particular multiplier k for which the inequality holds beyond some minimum x.
In Little-o, it must be that there is a minimum x after which the inequality holds no matter how small you make k, as long as it is not negative or zero.
These both describe upper bounds, although somewhat counter-intuitively, Little-o is the stronger statement. There is a much larger gap between the growth rates of f and g if f ∈ o(g) than if f ∈ O(g).
One illustration of the disparity is this: f ∈ O(f) is true, but f ∈ o(f) is false. Therefore, Big-O can be read as "f ∈ O(g) means that f's asymptotic growth is no faster than g's", whereas "f ∈ o(g) means that f's asymptotic growth is strictly slower than g's". It's like
<=versus<.More specifically, if the value of g(x) is a constant multiple of the value of f(x), then f ∈ O(g) is true. This is why you can drop constants when working with big-O notation.
However, for f ∈ o(g) to be true, then g must include a higher power of x in its formula, and so the relative separation between f(x) and g(x) must actually get larger as x gets larger.
To use purely math examples (rather than referring to algorithms):
The following are true for Big-O, but would not be true if you used little-o:
The following are true for little-o:
Note that if f ∈ o(g), this implies f ∈ O(g). e.g. x² ∈ o(x³) so it is also true that x² ∈ O(x³), (again, think of O as
<=and o as<)Big-O 与 Little-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)，因为它仍然有一个lim。 sup: 4.)我建议记住 Big-O 表示法如何转换为渐近比较。比较更容易记住，但灵活性较差，因为您不能说 nO(1) = P 之类的东西。
Big-O is to little-o as
≤is to<. Big-O is an inclusive upper bound, while little-o is a strict upper bound.For example, the function
f(n) = 3nis:O(n²),o(n²), andO(n)O(lg n),o(lg n), oro(n)Analogously, the number
1is:≤ 2,< 2, and≤ 1≤ 0,< 0, or< 1Here's a table, showing the general idea:
(Note: the table is a good guide but its limit definition should be in terms of the superior limit instead of the normal limit. For example,
3 + (n mod 2)oscillates between 3 and 4 forever. It's inO(1)despite not having a normal limit, because it still has alim sup: 4.)I recommend memorizing how the Big-O notation converts to asymptotic comparisons. The comparisons are easier to remember, but less flexible because you can't say things like nO(1) = P.
我发现当我无法从概念上掌握某些东西时，思考为什么要使用 X 有助于理解 X。（并不是说你没有尝试过，我只是在做准备.)
你知道的东西：对算法进行分类的一种常见方法是按运行时，通过引用算法的大哦复杂性，你可以很好地估计哪个算法“更好” - - 以 O! 中具有“最小”功能的为准即使在现实世界中，O(N) 也比 O(N²) “更好”，除非是超大质量常数等愚蠢的事情。
假设有一些算法的运行时间为 O(N)。相当不错吧？但假设你（你这个聪明人）想出了一个运行时间复杂度为 O(N⁄loglogloglogN) 的算法。耶！它更快！但当你写论文时，一遍又一遍地写这些，你会觉得很愚蠢。所以你写一次，你就可以说“在这篇论文中，我已经证明了算法 X，以前可以在 O(N) 时间内计算，实际上可以在 o(n) 中计算。”
因此，每个人都知道你的算法更快——具体快多少尚不清楚，但他们知道它更快。理论上来说。 :)
I find that when I can't conceptually grasp something, thinking about why one would use X is helpful to understand X. (Not to say you haven't tried that, I'm just setting the stage.)
Stuff you know: A common way to classify algorithms is by runtime, and by citing the big-Oh complexity of an algorithm, you can get a pretty good estimation of which one is "better" -- whichever has the "smallest" function in the O! Even in the real world, O(N) is "better" than O(N²), barring silly things like super-massive constants and the like.
Let's say there's some algorithm that runs in O(N). Pretty good, huh? But let's say you (you brilliant person, you) come up with an algorithm that runs in O(N⁄loglogloglogN). YAY! Its faster! But you'd feel silly writing that over and over again when you're writing your thesis. So you write it once, and you can say "In this paper, I have proven that algorithm X, previously computable in time O(N), is in fact computable in o(n)."
Thus, everyone knows that your algorithm is faster --- by how much is unclear, but they know its faster. Theoretically. :)
一般来说
，渐近符号可以理解为：缩小时函数如何比较？（测试这一点的一个好方法就是使用像 Desmos 并使用鼠标滚轮进行游戏）。特别是：
f(n) ∈ o(n)表示：在某些时候，缩小得越多，f(n)就越会被n所支配（它将逐渐偏离它）。g(n) ∈ θ(n)表示：在某些情况下一点，缩小不会改变g(n)与n的比较（如果我们从轴上删除刻度，您将无法分辨缩放级别）。最后，
h(n) ∈ O(n)意味着函数h可以属于这两个类别中的任何一个。它可以看起来很像n，也可以在n增加时越来越小于n。基本上，f(n)和g(n)也在O(n)中。我认为这个维恩图（改编自本课程）可以帮助：
这与我们用于比较数字的内容完全相同：
在计算机科学中
在计算机科学中，人们通常会证明给定的算法承认上界
O和下界In general
Asymptotic notation is something you can understand as: how do functions compare when zooming out? (A good way to test this is simply to use a tool like Desmos and play with your mouse wheel). In particular:
f(n) ∈ o(n)means: at some point, the more you zoom out, the moref(n)will be dominated byn(it will progressively diverge from it).g(n) ∈ Θ(n)means: at some point, zooming out will not change howg(n)compare ton(if we remove ticks from the axis you couldn't tell the zoom level).Finally
h(n) ∈ O(n)means that functionhcan be in either of these two categories. It can either look a lot likenor it could be smaller and smaller thannwhennincreases. Basically, bothf(n)andg(n)are also inO(n).I think this Venn diagram (adapted from this course) could help:
It's the exact same has what we use for comparing numbers:
In computer science
In computer science, people will usually prove that a given algorithm admits both an upper
Oand a lower bound????. When both bounds meet that means that we found an asymptotically optimal algorithm to solve that particular problemΘ.For example, if we prove that the complexity of an algorithm is both in
O(n)and????(n)it implies that its complexity is inΘ(n). (That's the definition ofΘand it more or less translates to "asymptotically equal".) Which also means that no algorithm can solve the given problem ino(n). Again, roughly saying "this problem can't be solved in (strictly) less thannsteps".Usually the
ois used within lower bound proof to show a contradiction. For example:Details about lower/upper bound meanings
An upper bound of
O(n)simply means that even in the worse case, the algorithm will terminate in at mostnsteps (ignoring all constant factors, both multiplicative and additive). A lower bound of????(n)is a statement about the problem itself, it says that we built some example(s) where the given problem couldn't be solved by any algorithm in less thannsteps (ignoring multiplicative and additive constants). The number of steps is at mostnand at leastnso this problem complexity is "exactlyn". Instead of saying "ignoring constant multiplicative/additive factor" every time we just writeΘ(n)for short.大 O 表示法有一个同伴，称为小 O 表示法。大 O 表示法表示一个函数
不比另一个函数渐近。为了表示一个函数渐近小于另一个函数，我们使用小-o 表示法。大 O 和小 O 表示法之间的差异类似于 <= （小于等于）和 <= 之间的差异。 （少于）。The big-O notation has a companion called small-o notation. The big-O notation says the one function is asymptotical
no more thananother. To say that one function is asymptoticallyless thananother, we use small-o notation. The difference between the big-O and small-o notations is analogous to the difference between <= (less than equal) and < (less than).