困惑于小O的意思(Confused on Little O meaning)

困惑于小O的意思(Confused on Little O meaning)

所以我从小页面中获取的是当你应用小O符号时我们必须检查一个速率是否比另一个速率快（小o聚焦于上限）？

在这种情况下，当我们申请小o：

2 ^ n = o（3 ^ n）将为假，因为2 ^ n和3 ^ n上限速度相等但不低于

2n = o（n ^ 2）为真，因为n ^ 2上限为2且2n不具有上限。

我是在正确的轨道上吗？

So what I took from little o page is when you apply the small O notation we have to check if one rate is faster then the other (small o focuses on the upper bound)?

In this case when we apply small o:

2^n = o(3^n) will be false as 2^n and 3^n upper bound is equal in speed but not less then

2n = o(n^2) is true as n^2 upper bound is 2 and 2n does not have an upper bound.

Am I on the right track?

最满意答案

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

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

Simmilarly。 对于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)

2^n is in o(3^n) (little o), since:

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

Simmilarly. for 2n, it is easy to show that it is in o(n^2)

An intuitive for "little o" is - it's an upper bound, but not a tight one. It means, a function f(n) is in o(g(n)) if f(n) is in O(g(n)), but not in Omega(g(n)).

In your example, 2^n is in O(3^n), but it is not in Omega(3^n), so we can say it is in o(3^n)