f∈O(g)表示

对于至少一个常数k > 0，你可以找到一个常数a，使得不等式0 <= f(x) <= k g(x)对所有x > a成立。

注意，O(g)是满足这个条件的所有函数的集合。

F∈o(g)表示

对于每一个常数k > 0，你可以找到一个常数a，使得不等式0 <= f(x) < k g(x)对所有x > a成立。

同样，注意o(g)是一个集合。

在Big-O中，你只需要找到一个特定的乘数k，它的不等式大于某个最小值x。

在Little-o中，必须有一个最小x，在这个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就不正确了:

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为<=，o为<)

大o之于小o，就像≤之于<。Big-O是包容性的上界，而little-o是严格的上界。

例如，函数f(n) = 3n为:

O(n²)O(n²)O(n) 不是O(lgn) O(lgn)或O(n)

类似地，数字1是:

≤2,< 2,和≤1 不是≤0,< 0,或者< 1

下面是一个表格，展示了大致的想法:

(注:该表是一个很好的指南，但其极限定义应根据上极限而不是正常极限。例如，3 + (n mod 2)永远在3和4之间振荡。它在O(1)，尽管没有正常的限制，因为它仍然有一个lim sup: 4。)

我建议大家记住大o符号是如何转化为渐近比较的。比较更容易记住，但不太灵活，因为你不能说nO(1) = P。

我发现当我不能从概念上理解某件事情时，思考为什么人们会使用X有助于理解X(并不是说你没有尝试过，我只是在铺垫)。

你知道的东西:一种常用的算法分类方法是通过运行时，通过引用算法的大复杂度，你可以很好地估计哪个是“更好的”——哪个在O中有“最小的”函数!即使在现实世界中，O(N)也比O(N²)“更好”，除非有一些愚蠢的东西，比如超大质量常数之类的。

假设有某种算法在O(N)范围内运行。不错吧?但假设你(你这个聪明的人)提出了一个算法，在O(N⁄loglogloglogN)中运行。耶!它的速度!但是当你写论文的时候，你会觉得一遍又一遍地写这个很傻。你写一次，你可以说"在这篇论文中，我证明了算法X，之前在O(N)时间内可计算，实际上在O(N)时间内也可计算"

因此，每个人都知道你的算法更快——快多少还不清楚，但他们知道它更快。从理论上讲。：）

大o符号有一个同伴叫做小o符号。大o符号表示一个函数和另一个函数一样是渐近的。为了说明一个函数渐进地小于另一个函数，我们使用小o符号。大o和小o符号之间的差异类似于<=(小于等于)和<(小于)之间的差异。