第6章：渐近符号大欧米茄和Theta-AJ'DS和ALGO的指南

在本章中，我们将学习以下主题：

在上一章中，我们了解了定义严格上限的Big O符号。在本章中，我们将了解“大欧米茄”和“大Theta”符号。

6.1大欧米茄Ω：

该符号用于表示严格的下限。大欧米茄可以定义为：

对于一个函数，如果存在一个常数C和n0，则f（n）等于Ω（g（n）），使得f（n）始终大于C（g（n））。即f（n）> C(g(n)) or C(g(n)) < f(n).

f（n）= 2n + 3和g（n）= n

然后我们需要将f（n）减少到g（n）。

现在，当C = 1时，我们将能够满足条件。

即（2n + 3）> (1*n) for all n >=1.

因此我们可以说f（n）等于Ω（n）。

因此，从以上示例中我们可以得出以下图像。

大theta用于获取函数的平均大小写。可以定义为：

对于函数f（n）如果函数f（n）大于C1 g（n）且小于所有n个C2g（n），则f（n）等于Ø（n）>=0。这意味着函数f（n）始终在C1 * g（n）和C2 * g（n）之间。可以在公式中显示为：C1 g（n）<= f(n) <= C2 g(n).

换句话说，如果您想证明大theta，则分别找出大O和大Omega，便可以证明大theta。

让我们以一个例子来了解大Theta：

给定f（n）= 5n ^ 2 + 2n + 1

g（n）= n ^ 2

我们需要证明C1 g（n）<= f(n) <= C2 g(n)

c1 = 5和c2 = 8且n1 = 1

5 * 1<=（5（1 ^ 2）+ 2 * 1 +1<= 8 * 1

因此证明f（n）=Ø（n ^ 2）。