algorithm - 如何证明 Θ(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).