Big O 和 Big Omega 是一样的，但相反？

Question

这是真的？

f(n) = O(g(n))  === g(n) = Omega(f(n))

基本上它们可以互换，因为它们是对立的吗？

那么如果 F 在 G 的 Big O 中，那么 G 是 F 的 Big Omega？

Answer 1

查看定义会有所帮助：

f(n) is in O(g(n)) if and only if:
There are positive constants c and k, such that 0 ? f(n) ? cg(n) for all n ? k.


g(n) is in Omega(f(n)) if and only if: 
There are positive constants c and k, such that g(n)  ? cf(n)  ? 0 for all n ? k.  

如果你能找到使 f(n) 在 O(g(n)) 中的 c 和 k 的值，那么相同的值也会显示 g(n) 是 Omega(f(n))（只需将两边分开c) 的不等式。这就是它们可以互换的原因。

F(n) 不是 Theta(g(n))，除非它同时在 O(g(n) 和 Omega(g(n)) 中。

希望有帮助！