algorithm - 对小O的含义感到困惑

Question

所以我从little o 页面得到的是，当您应用 small O 表示法时，我们必须检查一个速率是否比另一个快（small o 关注上限）？

在这种情况下，当我们应用小 o 时：

2^n = o(3^n) 将是错误的，因为 2^n 和 3^n 上限在速度上相等但不少于

2n = o(n^2) 为真，因为 n^2 上限为 2 且 2n 没有上限。

我在正确的轨道上吗？

Answer 1

2^n在o(3^n)（小 o）中，因为：

lim_n->infinity (2^n / 3^n) = 0

同样。因为2n，很容易证明它在o(n^2)

“little o”的直观含义是 - 它是一个上限，但不是一个严格的上限。这意味着，如果 f(n) 在 中，则函数在 中f(n)，但不在 中。o(g(n))O(g(n))Omega(g(n))

在您的示例中，2^n是 in O(3^n)，但不是 in Omega(3^n)，所以我们可以说它是 ino(3^n)

Answer 2

大 O 和小 O 之间的唯一区别是大 O 允许函数在相等的阶段增长，但是小 O 表明 g(x) 具有更高的增长率并且在特定点 x' 之后永远不可能相等（考虑f(x)=o(g(x))

您提供的第一个示例是错误的，因为小 O 指出：对于 f(x)=o(g(x)) |f(x)|x'

然而，在上述 f(x)=2^x 和 g(x)=3^x 的情况下，不存在 C 和 x' 来满足它，因为 g(x) 具有更高的增长率。

如果您了解大 O，那么定义小 O 的最佳方法是：

如果一个函数是大 O 而不是大欧米茄，则该函数称为小 O——这是因为大欧米茄和大 O 仅在两个函数 s 的增长率相等的情况下相交，所以如果我们删除该特定情况，它是小O。

但是请记住，如果 f(x) 是 Big O g(x)，它也可以是 g(x) 的小 O，但反之亦然是不可能的。