大 Ө 符号到底代表什么？
我对大 O、大 Omega 和大 Theta 符号之间的区别感到非常困惑。
我知道大 O 是上限，大 Omega 是下限，但是 big Ө (theta) 到底代表什么？
我读过这意味着紧密绑定，但这是什么意思？
首先让我们了解什么是大 O、大 Theta 和大 Omega。它们都是 sets 的函数。
Big O 给出上限 asymptotic bound，而大 Omega 给出下限。 Big Theta 两者兼而有之。
Ө(f(n)) 的所有内容也是 O(f(n))，但反之则不然。如果 T(n) 同时在 O(f(n)) 和 Omega(f(n)) 中，则称它在 Ө(f(n)) 中。
在集合术语中，Ө(f(n)) 是 O(f(n)) 和 Omega(f(n)) 的 intersection
例如，归并排序最坏情况是 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)。另一方面，big-Omega 说有一个常数 C2 使得 T(n) >= C2 * f(n)))。
不要混淆！
不要与最坏、最好和平均情况分析相混淆：所有三个（Omega、O、Theta）表示法都与算法的最佳、最坏和平均情况分析无关。这些中的每一个都可以应用于每个分析。
我们通常用它来分析算法的复杂性（如上面的归并排序示例）。当我们说“算法 A 是 O(f(n))”时，我们真正的意思是“在最差1 案例分析下的算法复杂度是 O(f(n))” - 意思是 - 它缩放“相似”（或正式，不比）函数f(n)差。
为什么我们关心算法的渐近界？
嗯，有很多原因，但我相信其中最重要的是：
确定确切的复杂度函数要困难得多，因此我们在 big-O/big-Theta 符号上“妥协”，这些符号在理论上足够丰富。确切的操作数也取决于平台。例如，如果我们有一个包含 16 个数字的向量（列表）。需要多少操作？答案是：视情况而定。一些 CPU 允许向量加法，而另一些则不允许，因此答案在不同的实现和不同的机器之间有所不同，这是一个不受欢迎的属性。然而，大 O 符号在机器和实现之间更加稳定。
https://i.stack.imgur.com/kOUFl.png
很明显，f(n) = 2*n 比 f(n) = n“差”。但差异并不像其他功能那么大。我们可以看到 f(n)=logn 迅速变得比其他函数低得多，而 f(n) = n^2 迅速变得比其他函数高得多。
所以 - 由于上述原因，我们“忽略”了常数因子（图表示例中的 2*），而仅采用大 O 表示法。
在上面的示例中，f(n)=n, f(n)=2*n 将在 O(n) 和 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通常，但并非总是如此。当缺少分析类（最差、平均和最佳）时，我们的意思是最坏的情况。
这意味着该算法在给定函数中既是大 O 又是大欧米茄。
例如，如果它是 Ө(n)，那么有一些常数 k，这样你的函数（运行时，无论如何），对于足够大的 n 大于 n*k，还有一些其他常数 {5 } 以使您的函数小于 n*K 以获得足够大的 n。
换句话说，对于足够大的 n，它夹在两个线性函数之间：
对于足够大的 k < K 和 n，n*k < f(n) < n*K
Theta(n)： 函数 f(n) 属于 Theta(g(n))，如果存在正常数 c1 和 c2，使得 f(n) 可以夹在 c1(g(n)) 和 {7 之间}。即它给出了上限和下限。
Theta(g(n)) = { f(n) : 存在正常数 c1,c2 和 n1 使得 0<=c1(g(n))<=f(n)<=c2(g(n))对于所有 n>=n1 }
当我们说 f(n)=c2(g(n)) 或 f(n)=c1(g(n)) 时，它表示渐近紧界。
O(n)：它只给出上限（可能很紧也可能不紧）
O(g(n)) = { f(n) : 存在正常数 c 和 n1 使得 0<=f(n)<=cg(n) 对于所有 n>=n1}
ex：界限 2*(n^2) = O(n^2) 是渐近紧的，而界限 2*n = O(n^2) 不是渐近紧的。
o(n)：它只给出上限（从不严格限制）
O(n) 和 o(n) 之间的显着区别是对于所有 n>=n1，f(n) 小于 cg(n)，但不等于 O(n)。
ex：2*n = o(n^2)，但 2*(n^2) != o(n^2)
https://i.stack.imgur.com/nLm8w.png
大 Theta 符号：
没什么好惹的哥们！！
如果我们有一个正值函数 f(n) 并且 g(n) 接受一个正值参数 n 则 ϴ(g(n)) 定义为 {f(n):对于所有 n> 存在常数 c1,c2 和 n1 =n1}
其中 c1 g(n)<=f(n)<=c2 g(n)
举个例子：
https://i.stack.imgur.com/NmWqN.gif
https://i.stack.imgur.com/CIjOK.gif
c1=5 和 c2=8 和 n1=1
在所有符号中，ϴ 符号给出了关于函数增长率的最佳直觉，因为它给了我们一个紧密的界限，不像 big-oh 和 big-omega 分别给出上限和下限。
ϴ 告诉我们 g(n) 尽可能接近 f(n)，g(n) 的增长率尽可能接近 f(n) 的增长率。
https://i.stack.imgur.com/OelP2.gif
首先是理论
Big O = 上限 O(n) Theta = 阶函数 - theta(n) Omega = Q-Notation(Lower Limit) Q(n)
为什么人们如此困惑？
在许多博客和书籍中，如何强调这一声明就像
“这是大 O(n^3)”等。
人们经常像天气一样混淆
O(n) == theta(n) == Q(n)
但值得记住的是，它们只是名称为 O、Theta 和 Omega 的数学函数
所以它们具有相同的多项式通式，
让，
f(n) = 2n4 + 100n2 + 10n + 50 那么，
g(n) = n4，所以 g(n) 是以函数为输入并返回具有最大幂的变量的函数，
相同的 f(n) 和 g(n) 用于以下所有解释
大 O(n) - 提供上限
大 O(n4) = 3n4，因为 3n4 > 2n4
3n4 是 Big O(n4) 的值 就像 f(x) = 3x
n4 在这里扮演 x 的角色，所以，
用 x'so 替换 n4，Big O(x') = 2x'，现在我们都很高兴一般概念是
所以 0 ≤ f(n) ≤ O(x')
O(x') = cg(n) = 3n4
投入价值，
0 ≤ 2n4 + 100n2 + 10n + 50 ≤ 3n4
3n4 是我们的上限
Big Omega(n) - 提供下限
Theta(n4) = cg(n) = 2n4 因为 2n4 ≤ 我们的示例 f(n)
2n4 是 Theta(n4) 的值
所以，0 ≤ cg(n) ≤ f(n)
0 ≤ 2n4 ≤ 2n4 + 100n2 + 10n + 50
2n4 是我们的下限
Theta(n) - 提供紧界
计算得出天气下界与上界相似，
情况1）。上限类似于下限
if Upper Bound is Similar to Lower Bound, The Average Case is Similar
Example, 2n4 ≤ f(x) ≤ 2n4,
Then Theta(n) = 2n4
案例2）。如果上界与下界不相似
In this case, Theta(n) is not fixed but Theta(n) is the set of functions with the same order of growth as g(n).
Example 2n4 ≤ f(x) ≤ 3n4, This is Our Default Case,
Then, Theta(n) = c'n4, is a set of functions with 2 ≤ c' ≤ 3
希望这解释！
f(n) = n^2渐近强于n，因此是 Omega(n)。但是它不是 O(n)（因为对于较大的n值，它大于c*n，对于所有n）。既然我们说 Theta(n) 是 O(n) 和 Omega(n) 的交集，既然不是 O(n)，它也不能是 Theta(n)。T_best(n), T_worst(n), T_average(n)。它们不必相同（大多数情况下，它们不是相同的）。 O/Omega/Theta 可以独立应用于其中的任何一个。