我只是想了解Big O和Big Omega是如何工作的。我知道Big O的意思并不比O O好，Big Omega的意思并不比跑步时间差。因此，如果我有一个函数g（n）使得g（n）= O（f（n）），那么我能说f（n）=Ω（g（n））吗？
最佳答案
用符号表示，最好写g（n）∈O（f（n）），因为“ O（f（n））”可以看做是所有函数的集合，它们的增长速度不超过f的倍数（n）。
让我们重申一下复杂性理论中使用的两个相关的形式定义：
g（n）∈O（f（n））⇔∃k> 0∃N≥0∀n≥N[| g（n）| ≤k·| f（n）|]
f（n）∈Ω（g（n））⇔∃k> 0∃N≥0∀n≥N[f（n）≥k·g（n）]
如果我们可以假设f和g是非负函数（对于计算机科学中的函数几乎总是这样），那么我们可以删除绝对值符号。从而：
g（n）∈O（f（n））⇔∃k> 0∃N≥0∀n≥N[g（n）≤k·f（n）]
f（n）∈Ω（g（n））⇔∃k> 0∃N≥0∀n≥N[f（n）≥k·g（n）]
接下来，翻转第二个逻辑语句上的不等式：
g（n）∈O（f（n））⇔∃k> 0∃N≥0∀n≥N[g（n）≤k·f（n）]
f（n）∈Ω（g（n））⇔∃k> 0∃N≥0∀n≥N[k·g（n）≤f（n）]
现在，让我们证明第一条语句的右侧暗示着第二条语句的右侧：
假设∃k＞0∃N≥0∀n≥N[g（n）≤k·f（n）]为真。
实例化满足>N≥0∀n≥N[g（n）≤k·f（n）]的k> 0。
令kʹ= 1 / k，这是合法的，因为k≠0。
实例化满足≥n≥N的N≥0[g（n）≤k·f（n）]。
令n为任意数，以使n≥N。
那么我们有g（n）≤k·f（n）。
接下来，我们有g（n）/ k≤f（n）。
通过替换，我们有kʹ·g（n）≤f（n）。
因为n是任意的，所以我们得出∀n≥N[kʹ·g（n）≤f（n）]。
我们推导出满足∃n≥N的∃N≥0[kg·g（n）≤f（n）]。
我们得出thatk> 0∃N≥0∀n≥N[kʹ·g（n）≤f（n）]。
我们将kʹ重命名为k，使得∃k> 0∃N≥0∀n≥N[k·g（n）≤f（n）]。
因此，[∃k> 0∃N≥0∀n≥N[g（n）≤k·f（n）]]表示[∃k> 0∃N≥0∀n≥N[k·g（n）≤ f（n）]]。
因此，根据需要，g（n）∈O（f（n））意味着f（n）∈Ω（g（n））。