首先让我们了解什么是大 O、大 Theta 和大 Omega。它们都是函数集。

大 O 给出渐近上界，而大欧米茄给出下界。Big Theta 两者兼而有之。

一切都是Ө(f(n))，O(f(n))但不是相反。 如果它同时在 in和 in中
T(n)，则称在in 中。在集合术语中，是***和的*交集Ө(f(n))``O(f(n))``Omega(f(n))

Ө(f(n))``O(f(n))``Omega(f(n))

例如，归并排序最坏的情况是两者O(n*log(n))和Omega(n*log(n))- 因此也是Ө(n*log(n))，但它也是O(n^2)，因为n^2它比它渐近地“更大”。然而，它不是 Ө(n^2)，因为算法不是Omega(n^2)。

更深入的数学解释

O(n)是渐近上界。如果T(n)是O(f(n))，则表示从某一个开始n0，有一个常数C这样的T(n) <= C * f(n)。另一方面，大欧米茄说有一个常数C2使得T(n) >= C2 * f(n)))。

不要混淆！

不要与最坏、最好和平均情况分析相混淆：所有三个（Omega、O、Theta）表示法都与算法的最佳、最坏和平均情况分析无关。这些中的每一个都可以应用于每个分析。

我们通常使用它来分析算法的复杂性（如上面的归并排序示例）。当我们说“算法 A 是O(f(n))”时，我们真正的意思是“在最坏的1情况分析下的算法复杂度是O(f(n))”——意思是——它缩放“相似”（或正式地，不比）函数f(n)。

为什么我们关心算法的渐近界？

嗯，有很多原因，但我相信其中最重要的是：

1. 确定确切的复杂度函数要困难得多，因此我们在 big-O/big-Theta 符号上“妥协”，这些符号在理论上足够丰富。
2. 确切的操作数也取决于平台。例如，如果我们有一个包含 16 个数字的向量（列表）。需要多少操作？答案是：视情况而定。一些 CPU 允许向量加法，而另一些则不允许，因此答案在不同的实现和不同的机器之间有所不同，这是一个不受欢迎的属性。然而，大 O 符号在机器和实现之间更加稳定。

要演示此问题，请查看以下图表：

很明显，它f(n) = 2*n比f(n) = n. 但差异并不像其他功能那么大。我们可以看到，它f(n)=logn迅速变得比其他功能低得多，并且f(n) = n^2迅速变得比其他功能高得多。
所以 - 由于上述原因，我们“忽略”了常数因子（图表示例中的 2*），并且只采用大 O 表示法。

在上面的示例中，f(n)=n, f(n)=2*n将同时在 inO(n)和 in Omega(n)- 中，因此也将在Theta(n).
另一方面 -f(n)=logn将在O(n)（它比“更好” f(n)=n），但不会在Omega(n)- 因此也不会在Theta(n).
对称地，f(n)=n^2将在Omega(n)，但不在O(n)，因此 - 也不是Theta(n)。

1通常，但并非总是如此。当缺少分析类（最差、平均和最佳）时，我们的意思是最坏的情况。