g(n) ∈ O(f(n)) 是否意味着 f(n) ∈ Ω(g(n))？

Question

我只是想了解 Big O 和 Big Omega 的工作原理。我知道Big O的意思是不比，Big Omega的意思是不比运行次差。所以如果我有一个函数 g(n) 这样 g(n ) = O(f(n)) 那么我可以说 f(n) = Ω(g(n) )?

Answer 1

符号方面，最好写成 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)]

现在让我们证明第一个语句的右边蕴含第二个语句的右边：

1. 假设∃k>0∃N≥0∀n≥N[g(n)≤k·f(n)] 为真。
2. 实例化满足∃N≥0的k>0 ∀n≥N [g(n) ≤ k·f(n)].
3. 令kʹ = 1/k，这是合法的，因为k≠0 .
4. 实例化满足∀n≥N[[=20的N≥0 =]g(n) ≤ k·f(n)].
5. 设n为任意数，使得n≥N.
6. 那么我们有 g(n) ≤ k· f(n).
7. 接下来我们有 g(n)/k ≤ f(n).
8. 通过代入，我们有 kʹ·g(n) ≤ f(n).
9. 因为n是任意的，我们推导出∀n≥N[kʹ·g(n)≤f(n)].
10. 我们推导出∃N≥0满足∀n≥N[kʹ·g(n) ≤ f(n)].
11. 我们推导出∃kʹ>0 ∃N≥0 ∀n≥N [kʹ·g(n) ≤ f(n)].
12. 我们将kʹ重命名为k，这样∃k>0∃N≥0∀n≥N[k·g(n) ≤ f(n)].
13. 因此[∃k>0∃N≥0∀n≥N[g(n)≤k·f(n)]] 意味着 [∃k>0 ∃N≥0∀n≥N[k·g(n) ≤ f(n)]].
14. 因此g(n)∈O(f( n)) 意味着 f(n) ∈ Ω(g(n)), 随心所欲.