algorithm - 算法 - Little o 和 Big Omega 在相同的功能上？

Question

我有两个功能，f(n),g(n)例如f(n)=o(g(n)).

说清楚，我拿了一点

有了给我的信息，这是可能的f(n)=Omega(g(n))。

对我来说，这听起来不可能，因为 Little-o 定义对我说

for every c>0,f(n)<c * g(n).

谢谢！

Answer 1

不，这并不能保证。有时，大 O 与 Omega(g(n)) 相同，但并非一直如此。

Answer 2

让我们假设 f 和 g 都是严格正的。

f(n) = o(g(n)) 表示 f(n)/g(n) -> 0 因为 n 趋于无穷大。

f(n) = Ω(g(n)) 意味着（假设 Ω 的 Knuth 定义） g(n) = O(f(n))，这意味着存在一个 c>0 使得对于足够大的 n，g(n ) <= cf(n)。但是，对于足够大的 n，f(n)/g(n) >= 1/c > 0。所以 f(n)/g(n) -> 0 不可能，因为 n 趋于无穷大，这意味着f(n) = Ω(g(n)) 和 f(n) = o(g(n)) 是不可能的。