大Ө符号代表什么？
我对大O，大欧米茄和大西塔符号之间的差异感到困惑。
我明白，大O是上界，大Omega是下界，但大Ө（θ）究竟代表什么？
我已经读过这意味着紧张的限制 ，但这意味着什么？
这意味着该算法在给定函数中既是大O又是大Omega。
例如，如果它是Ө(n) ，那么存在一些常数k ，使得你的函数（运行时间，无论什么）大于n*k对于足够大的n以及其他常数K ，使得你的函数对于足够大的n小于n*K
换句话说，对于足够大的n ，它夹在两个线性函数之间：
对于k < K和n足够大， n*k < f(n) < n*K
首先让我们了解什么是大O，大西塔和大欧米茄。 它们都是一套功能。
大O给出了上限渐近界，而大欧米茄给出了一个下界。 Big Theta给出了两个。
一切都是Ө(f(n))也是O(f(n)) ，但不是相反。
如果它在O(f(n))和Omega(f(n))则称T(n)在Ө(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)) ）。
不要混淆！
不要与最差，最好和平均情况分析混淆：所有三个（欧米茄，O，西塔）符号是不相关的算法最好，最差，平均情况分析。 这些中的每一个都可以应用于每个分析。
我们通常使用它来分析算法的复杂性 （如上面的合并排序示例）。 当我们说“算法A是O(f(n)) ”时，我们真正的意思是“最坏情况下分析的算法复杂度为O(f(n)) ” - 意思是它缩放“相似”（或正式，不逊于）函数f(n) 。
为什么我们关心算法的渐近界？
那么，这有很多原因，但我相信其中最重要的是：
为了演示这个问题，请看下面的图表： 
很明显， 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通常，尽管并非总是如此。 当分析类别（最差，最好和最差）缺失时，我们确实意味着最坏的情况。
为了回答你的问题，渐近符号中的渐近符号和函数也需要解释。 如果你有耐心阅读所有内容，最终情况会非常清楚。
1.渐近符号
想想算法，您可以使用2个主要思想：
我们可以说这个算法的运行时间增长为n ^ 2，系数为6，剩余项为100n + 300。这与我们使用的系数无关。 只要运行时间是^ 2 + bn + c，对于某些数字a> 0，b和c，总会有一个n的值，其中^ 2大于bn + c，并且这个差值随着n的增加而增加。 通过删除常数系数和不显着的项，我们使用渐近表示法。
2. Big-Theta
这是一个线性搜索的简单实现
var doLinearSearch = function(array) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess; // found it!
}
}
return -1; // didn't find it
};
当我们说一个特定的运行时间是Θ（n）时，我们说，一旦n变得足够大，运行时间至少为k 1 * n，而对于某些运行时间至多为k 2 * n常数k 1和k 2。 以下是如何考虑Θ（n） 
对于n的小值，我们不关心运行时间与k 1 * n或k 2 * n的比较。 但是，一旦n变得足够大 - 在虚线右侧或右侧 - 运行时间必须夹在k 1 * n和k 2 * n之间。 只要这些常数k 1和k 2存在，我们就说运行时间是Θ（n）。
3.渐近表示法中的函数
Θ（2 ^ n）的
请注意，指数函数a ^ n（其中a> 1）比任何多项式函数n ^ b增长更快，其中b是任何常数。
4.大O符号
5.大Ω（大欧米茄）符号
参考：https：//www.khanacademy.org
链接地址: http://www.djcxy.com/p/6795.html上一篇: What exactly does big Ө notation represent?
下一篇: What is the difference between a Generative and Discriminative Algorithm?