大O和小O表示法之间的区别

大O和小O表示法之间的区别

f∈O（g）说，本质上

对于 至少一个 常数 k > 0的选择，您可以找到一个常数 a ，使得不等式0 <= f（x）<= kg（x）对于所有x> a成立。

请注意，O（g）是该条件成立的所有函数的集合。

f∈o（g）说，本质上

对于常数 k > 0的 每个 选择，您都可以找到常数 a ，使得不等式0 <= f（x） a成立。

再次注意，o（g）是一个集合。

在Big-O中，仅需要找到一个特定的乘数 k， 对于该乘数 k ，不等式保持在某个最小值 x 之上。

在Little-o中，必须保证存在一个最小值 x ，只要将 k 设为负数或零，无论将 k 设为多小，不等式都成立。

两者都描述了上限，尽管有点违反直觉，Little-o是更强有力的陈述。如果f∈o（g），则f和g的增长率之间的差距比f∈O（g）时大得多。

差异的一个例证是：f∈O（f）为真，而f∈o（f）为假。因此，Big-O可以理解为“ f∈O（g）表示f的渐近增长不快于g’s，而“
f∈o（g）意味着f的渐近增长严格地慢于g’s”。就像

<=

vs 一样

<

。

更具体地说，如果g（x）的值是f（x）的常数倍，则f∈O（g）为真。这就是为什么在使用big-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视为

<

）