algorithm - 对 Little O 的意思感到困惑

Question

所以我从 little o page 中得到了什么是当您应用小 O 符号时，我们必须检查一个速率是否比另一个速率快(小 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)

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

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

中