big-o - O(f(n)) + Ω(g(n)) 是否等于 Ω(f(n)) + O(g(n))？

Question

下面的等式是真的吗？：

O(f(n)) + Ω(g(n)) = Ω(f(n)) + O(g(n))

我知道 Big O 的意思是不比 (function) 好，而 Big Omega 的意思是不比 (function) 差。但我不知道这是否使上述陈述为真或假。

标签： big-ocomputer-science

Answer 1

我们有三种一般情况（用于增加函数）：

• 案例 1： f(n) ∈ o(g(n))（注意“小哦”）。

  在这种情况下，O(f(n)) ⊂ O(g(n)) 和 Ω(g(n)) ⊂ Ω(f(n))。因此，O(f(n)) + Ω(g(n)) 是 O(g(n)) + Ω(f(n)) 的真子集。

  例如，如果 f(n) = n 且 g(n) = n ³，则 n ²在 Ω(f(n)) + O(g(n)) 中，但不在 O(f(n) 中)) + Ω(g(n))。

• 案例2： f(n) ∈ Θ(g(n))

  在这种情况下，O(f(n)) = O(g(n)) 和 Ω(g(n)) = Ω(g(n))，所以两组相等。

• 案例3： f(n) ∈ ω(g(n))

  这种情况相当于情况 1，只是f和g翻转了。所以通过对称性，我们有 O(f(n)) + Ω(g(n)) 是O(g(n)) + Ω(f(n))的适当超集。

总之，这两组一般不相等。