我真的很困惑大O，大欧米茄和大Theta符号之间的差异 .
我知道大O是上界，大欧米茄是下界，但大Ө（theta）究竟代表什么？
我读过它意味着 tight bound ，但这是什么意思？
这意味着该算法在给定函数中既是大O又是大Omega .
例如，如果它是 Ө(n) ，那么有一些常量 k ，这样你的函数（运行时，无论如何），对于足够大的 n 大于 n*k ，以及其他一些常量 K ，使得你的函数小于 n*K 足够大 n .
Ө(n)
k
n
n*k
K
n*K
换句话说，对于足够大的 n ，它夹在两个线性函数之间：
k < K 和 n 足够大 n*k < f(n) < n*K
k < K
n*k < f(n) < n*K
首先让我们了解大O，大Theta和大欧米茄是什么 . 它们都是sets的功能 .
大O给出了上半身asymptotic bound，而大欧米茄给出了下限 . Big Theta给出了两者 .
所有 Ө(f(n)) 也是 O(f(n)) ，但不是相反 .T(n) 据说在 Ө(f(n)) 中，如果它在 O(f(n)) 和 Omega(f(n)) 中 .在术语集中， Ө(f(n)) is the intersection of O(f(n)) and Omega(f(n))
Ө(f(n))
O(f(n))
T(n)
Omega(f(n))
例如，合并排序最坏情况是 O(n*log(n)) 和 Omega(n*log(n)) - 因此也是 Ө(n*log(n)) ，但它也是 O(n^2) ，因为 n^2 渐近"bigger"而不是它 . 但是，它是 not Ө(n^2) ，因为算法不是 Omega(n^2) .
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(n)
n0
C
T(n) <= C * f(n)
C2
T(n) >= C2 * f(n))
不要与最差，最佳和平均案例分析混淆：所有三种（Omega，O，Theta）符号都与算法的最佳，最差和平均案例分析相关 . 这些中的每一个都可以应用于每个分析 .
We usually use it to analyze complexity of algorithms （就像上面的合并排序示例） . 当我们说“算法A是 O(f(n)) ", what we really mean is "最差情况分析下的算法复杂度类似于”（或者正式，不差于）函数 f(n) 时 .
f(n)
嗯，有很多原因，但我相信其中最重要的是：
确定确切的复杂度函数要困难得多，因此我们对大O / big-Theta符号进行了分析，这些符号在理论上足够丰富 .
操作的确切数量也取决于平台 . 例如，如果我们有一个16个数字的向量（列表） . 需要多少操作？答案是：这取决于 . 一些CPU允许向量添加，而其他CPU则不允许，因此答案在不同的实现和不同的机器之间变化，这是不期望的属性 . 然而，大O符号在机器和实现之间更加恒定 .
要演示此问题，请查看以下图表：
很明显 f(n) = 2*n 是"worse"而不是 f(n) = n . 但差异并不像其他功能那么激烈 . 我们可以看到 f(n)=logn 很快就会比其他函数低得多，并且 f(n) = n^2 很快就会比其他函数高得多 .所以 - 由于上述原因，我们"ignore"常数因子（图中的2 *），并且只采用big-O表示法 .
f(n) = 2*n
f(n) = n
f(n)=logn
f(n) = n^2
在上面的示例中， f(n)=n, f(n)=2*n 将在 O(n) 和 Omega(n) 中 - 因此也将在 Theta(n) 中 .另一方面 - f(n)=logn 将在 O(n) （它是"better"而不是 f(n)=n ），但不会在 Omega(n) 中 - 因此也不会在 Theta(n) 中 .对称地， f(n)=n^2 将在 Omega(n) 中，但不在 O(n) 中，因此 - 也不是 Theta(n) .
f(n)=n, f(n)=2*n
Omega(n)
Theta(n)
f(n)=n
f(n)=n^2
1通常，虽然并非总是如此 . 当分析类（最差，平均和最佳）缺失时，我们的意思是 the worst case.
Theta(n): 函数 f(n) 属于 Theta(g(n)) ，如果存在正常数 c1 和 c2 ，则 f(n) 可以夹在 c1(g(n)) 和 c2(g(n)) 之间 . 即它既给出了上限，也给出了下限 .
Theta(g(n))
c1
c2
c1(g(n))
c2(g(n))
Theta（g（n））= {f（n）：存在正常数c1，c2和n1所有n> = n1} 0 <= c1（g（n））<= f（n）<= c2（g（n））
当我们说 f(n)=c2(g(n)) 或 f(n)=c1(g(n)) 时，它代表渐近紧束缚 .
f(n)=c2(g(n))
f(n)=c1(g(n))
O(n): 它只给出上限（可能或可能不紧）
O（g（n））= {f（n）：存在正常数c和n1，使得对于所有n> = n1，0 <= f（n）<= cg（n）
例如：边界 2*(n^2) = O(n^2) 渐近紧，而边界 2*n = O(n^2) 并非渐近紧 .
2*(n^2) = O(n^2)
2*n = O(n^2)
o(n): 它只给出上限（从不紧张）
O（n）和o（n）之间的显着差异是f（n）小于cg（n）所有n> = n1但不等于O（n） .
例如： 2*n = o(n^2) ，但 2*(n^2) != o(n^2)
2*n = o(n^2)
2*(n^2) != o(n^2)
什么搞乱伙伴！
如果我们有正值函数f（n）和g（n）取正值参数n那么Θ（g（n））定义为{f（n）：所有n都存在常数c1，c2和n1> = N1}
其中c1 g（n）<= f（n）<= c2 g（n）
设f（n）=
g（n）=
c1 = 5，c2 = 8，n1 = 1
在所有符号中，Θ符号给出了关于函数增长率的最佳直觉，因为它给我们一个紧密的约束，不像大哦和大ω分别给出上限和下限 .
Θ告诉我们g（n）与f（n）一样接近，g（n）的增长率尽可能接近f（n）的增长率 .
4 回答
这意味着该算法在给定函数中既是大O又是大Omega .
例如，如果它是
Ө(n)，那么有一些常量k，这样你的函数（运行时，无论如何），对于足够大的n大于n*k，以及其他一些常量K，使得你的函数小于n*K足够大n.换句话说，对于足够大的
n，它夹在两个线性函数之间：k < K和n足够大n*k < f(n) < n*K首先让我们了解大O，大Theta和大欧米茄是什么 . 它们都是sets的功能 .
大O给出了上半身asymptotic bound，而大欧米茄给出了下限 . Big Theta给出了两者 .
所有
Ө(f(n))也是O(f(n))，但不是相反 .T(n)据说在Ө(f(n))中，如果它在O(f(n))和Omega(f(n))中 .在术语集中， Ө(f(n)) is the intersection of O(f(n)) and Omega(f(n))
例如，合并排序最坏情况是
O(n*log(n))和Omega(n*log(n))- 因此也是Ө(n*log(n))，但它也是O(n^2)，因为n^2渐近"bigger"而不是它 . 但是，它是 notӨ(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）符号都与算法的最佳，最差和平均案例分析相关 . 这些中的每一个都可以应用于每个分析 .
We usually use it to analyze complexity of algorithms （就像上面的合并排序示例） . 当我们说“算法A是
O(f(n))", what we really mean is "最差情况分析下的算法复杂度类似于”（或者正式，不差于）函数f(n)时 .为什么我们关心算法的渐近界？
嗯，有很多原因，但我相信其中最重要的是：
确定确切的复杂度函数要困难得多，因此我们对大O / big-Theta符号进行了分析，这些符号在理论上足够丰富 .
操作的确切数量也取决于平台 . 例如，如果我们有一个16个数字的向量（列表） . 需要多少操作？答案是：这取决于 . 一些CPU允许向量添加，而其他CPU则不允许，因此答案在不同的实现和不同的机器之间变化，这是不期望的属性 . 然而，大O符号在机器和实现之间更加恒定 .
要演示此问题，请查看以下图表：
很明显
f(n) = 2*n是"worse"而不是f(n) = n. 但差异并不像其他功能那么激烈 . 我们可以看到f(n)=logn很快就会比其他函数低得多，并且f(n) = n^2很快就会比其他函数高得多 .所以 - 由于上述原因，我们"ignore"常数因子（图中的2 *），并且只采用big-O表示法 .
在上面的示例中，
f(n)=n, f(n)=2*n将在O(n)和Omega(n)中 - 因此也将在Theta(n)中 .另一方面 -
f(n)=logn将在O(n)（它是"better"而不是f(n)=n），但不会在Omega(n)中 - 因此也不会在Theta(n)中 .对称地，
f(n)=n^2将在Omega(n)中，但不在O(n)中，因此 - 也不是Theta(n).1通常，虽然并非总是如此 . 当分析类（最差，平均和最佳）缺失时，我们的意思是 the worst case.
Theta(n): 函数
f(n)属于Theta(g(n))，如果存在正常数c1和c2，则f(n)可以夹在c1(g(n))和c2(g(n))之间 . 即它既给出了上限，也给出了下限 .当我们说
f(n)=c2(g(n))或f(n)=c1(g(n))时，它代表渐近紧束缚 .O(n): 它只给出上限（可能或可能不紧）
例如：边界
2*(n^2) = O(n^2)渐近紧，而边界2*n = O(n^2)并非渐近紧 .o(n): 它只给出上限（从不紧张）
例如：
2*n = o(n^2)，但2*(n^2) != o(n^2)大Theta符号：
什么搞乱伙伴！
如果我们有正值函数f（n）和g（n）取正值参数n那么Θ（g（n））定义为{f（n）：所有n都存在常数c1，c2和n1> = N1}
其中c1 g（n）<= f（n）<= c2 g（n）
让我们举一个例子：
设f（n）=
g（n）=
c1 = 5，c2 = 8，n1 = 1
在所有符号中，Θ符号给出了关于函数增长率的最佳直觉，因为它给我们一个紧密的约束，不像大哦和大ω分别给出上限和下限 .
Θ告诉我们g（n）与f（n）一样接近，g（n）的增长率尽可能接近f（n）的增长率 .