如何证明 Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

Question

根据我的理解，Theta 位于 Big O 和 Omega 之间，我看到了这个说法，但我无法理解为什么交叉会出现在这里。我能否对 Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

进行数学和分析理解

Answer 1

Θ(g(n)) 表示函数上下都受 g(n) 约束。

在数学上，如果函数 f(n) 是 Θ(g(n))，那么

0 ≤ c₁.g(n) ≤ f(n) ≤ c₂.g(n) for all n greater than some constant k

---

现在，

• O(g(n)) 是 g(n) 的上界，所以 O(g(n)) 的函数是 g(n) 的上界。

• Ω(g(n)) 是 g(n) 的下界，因此 Ω(g(n)) 的函数是 g(n) 的下界。

O(g(n)) ∩ Ω(g(n))代表一个函数，从上下看都夹在g(n)之间，如下图所示，根据定义就是Θ(g(n)).

在数学上，这意味着函数是 0 ≤ c₁.g(n) ≤ f(n) ≤ c₂.g(n).