algorithm - 大哦，小哦和大θ关系

Question

如果函数 f(x)=O(g(x))，则有可能 f(x)=Ω(g(x)) 和 f(x)= ϴ(g(x)) , 但是如果 f(x)=o(g(x)), f(x)=Ω(g(x)), 或者 f(x)=ω(g(x)) 是可能的吗？

Answer 1

我们给出一些形式化的定义:

f(n) = o(g(n))
<=> forall c > 0 exists k > 0 s.t. 0 <= f(n) < cg(n) forall n >= k.
<=> g(n) = ω(f(n))

f(n) = O(g(n))
<=> exists c > 0 exists k > 0 s.t. 0 <= f(n) < cg(n) forall n >= k.
<=> g(n) = Ω(f(n))

f(n) = ϴ(g(n))
<=> f(n) = O(g(n)) and g(n) = O(f(n))

假设f(n) = o(g(n)) .问题一:可以f(n) = Ω(g(n)) ？如果是这样，则必须存在 c, k这样对于所有n >= k , 0 <= g(n) < cf(n) .从假设我们知道对于所有 c'存在一些 k'这样对于所有n >= k' , 0 <= f(n) < cg(n) .让k'' = max(k, k') .我们必须:

0 <= g(k'') < cf(k'')
0 <= f(k'') < c'g(k'')
=> 0 <= g(k'') < cc'g(k'')

这必须适用于 c' > 0 的任何选择.我们所知道的 c是存在的吗？但只要f(n)和 g(n)严格大于零，我们知道必须有一些最小的 c哪个有效。让c''是 c 的最小有效选择在 k'' .那么我们可以选择c' = 1/c'' .因此我们需要

0 < g(k'') < g(k'')

这总是错误的。所以只要f(n)和 g(n)不(最终)等于零，我们不能同时拥有 f(n) = o(g(n))和 f(n) = Ω(g(n)) .

自 f(n) = ω(g(n))暗示f(n) = Ω(g(n)) ，并且我们知道根据我们的假设后者不是真的，那么我们也可以安全地回答问题 2 是否定的。