困惑于小O的含义

2018-06-14 00:13:07

那么，我从小的页面上采取的是，当你应用小O符号时，我们必须检查一个速率是否比另一个更快（小o着重于上限）？

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

2 ^ n = o（3 ^ n）将是假的，因为2 ^ n和3 ^ n的上界速度相等但不小于

2n = o（n ^ 2）是真的，因为n ^ 2的上界是2，而2n没有上界。

我在正确的轨道上吗？

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)) O(g(n)) ，但不在Omega(g(n)) 。

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

大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的上述情况下，由于g（x）具有较高的生长速率，因此不存在C和x'来满足它。

如果您了解Big O，定义小O的最佳方式是：

一个函数被称为小O，如果它是大O但不是大Omega - 这是因为大Omega和大O只在函数s的groth比率相等的条件下相交，所以如果我们移除了特定的情况它是小O.

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

链接地址: http://www.djcxy.com/p/39895.html