大的区别
Big-O符号O(n)和Little-O符号o(n)什么区别？
本质上，f∈O（g）表示
对于常数k> 0的至少一个选择，可以找到一个常数a，使得对于所有x> a，不等式0 <= f（x）<= kg（x）。
请注意，O（g）是此条件成立的所有函数的集合。
基本上，f∈o（g）表示
对于常数k> 0的每一个选择，你可以找到一个常数a，使得对于所有x> a，不等式0 <= f（x）<kg（x）。
再次注意，o（g）是一个集合。
在Big-O中，只需要找到一个特定的乘数k，其中不等式超过某个最小值x即可。
在Little-o中，只要不是负数或零，就必须存在最小x，然后不等式成立。
这些都描述了上限，虽然有点反直觉，Little-o是更强的说法。 如果f∈o（g），f和g的增长率之间的差距比f∈0（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的幂，因此f（x）和g（x）之间的相对间隔实际上必须随x的增大而变大。
纯粹使用数学示例（而不是参考算法）：
对于Big-O，以下情况属实，但如果您使用little-o，则不会成立：
以下是小o的情况：
请注意，如果f∈o（g），这意味着f∈O（g）。 例如x²∈o（x³）所以x²∈O（x³）也是正确的（再次，将O视为<= ，o视为< ）
Big-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这样的东西。
我发现，当我无法从概念上理解某些东西时，想一想为什么要使用X有助于理解X.（并不是说你没有尝试过，我只是在设置舞台。）
[你知道的东西]对算法进行分类的一种常见方式是运行时，并且通过引用算法的大哦复杂性，可以很好地估计哪一个“更好” - 哪个具有“最小”函数在O！ 即使在现实世界中，O（N）比O（N 2）“更好”，除非超级巨量常量等愚蠢的东西。[/你知道的东西]
假设有一些算法在O（N）中运行。 很好，是吧？ 但是让我们说你（你这个聪明的人）提出了一个运行在O（N / loglogloglogN）中的算法。 好极了！ 它更快！ 但是当你写论文时，你会一遍又一遍地感到无聊。 所以你写了一次，你可以说“在本文中，我已经证明算法X，以前可以在时间O（N）上计算，实际上可以在o（n）中计算。”
因此，每个人都知道你的算法更快 - 多少不清楚，但他们知道它的速度更快。 理论上。 :)
链接地址: http://www.djcxy.com/p/1033.html