有时我看到 Θ(n) 带有奇怪的 Θ 符号，中间有东西，有时只是 O(n)。只是懒惰打字，因为没有人知道如何输入这个符号，还是意味着不同的东西？
martinus
问问题
213410 次
9 回答
632
简短说明：
如果一个算法是 Θ(g(n))，这意味着随着 n（输入大小）变大，算法的运行时间与 g(n) 成正比。
如果一个算法是 O(g(n))，这意味着随着 n 变大，算法的运行时间最多与 g(n) 成正比。
通常，即使人们谈论 O(g(n)) 他们实际上是指 Θ(g(n)) 但从技术上讲，还是有区别的。
从技术上讲：
O(n) 表示上限。Θ(n) 表示紧界。Ω(n) 表示下限。
f(x) = Θ(g(x)) 当且仅当 f(x) = O(g(x)) 且 f(x) = Ω(g(x))
基本上，当我们说一个算法是 O(n) 时，它也是 O(n 2 )、O(n 1000000 )、O(2 n )，...但是 Θ(n) 算法不是Θ(n 2 ) .
事实上，由于 f(n) = Θ(g(n)) 意味着对于足够大的 n 值，对于某些 c值，f(n) 可以限制在 c 1 g(n) 和 c 2 g(n) 内1和c 2，即f 的增长率渐近地等于g：g 可以是f 的下界和上界。这直接意味着 f 可以是 g 的下限和上限。最后，
f(x) = Θ(g(x)) 当且仅当 g(x) = Θ(f(x))
类似地，要证明 f(n) = Θ(g(n))，只要证明 g 是 f 的上界（即 f(n) = O(g(n))）而 f 是 f 的下界就足够了g (即 f(n) = Ω(g(n)) 这与 g(n) = O(f(n)) 完全相同。简而言之，
f(x) = Θ(g(x)) 当且仅当 f(x) = O(g(x)) 且 g(x) = O(f(x))
还有 little-oh 和 little-omega ( ω) 符号表示函数的松散上限和松散下限。
总结一下：
f(x) = O(g(x))(big-oh) 表示 的增长率f(x)逐渐小于或等于的增长率g(x)。
f(x) = Ω(g(x))(big-omega) 表示 的增长率f(x)逐渐大于或等于的增长率g(x)
f(x) = o(g(x))(little-oh) 表示 的增长率f(x)逐渐小于的增长率g(x)。
f(x) = ω(g(x))(little-omega) 表示 的增长率f(x)逐渐大于的增长率g(x)
f(x) = Θ(g(x))(theta) 表示 的增长率渐近f(x)地等于g(x)
有关更详细的讨论，您可以阅读 Wikipedia 上的定义或查阅经典教科书，例如 Cormen 等人的算法介绍。
于 2009-01-22T23:00:00.597 回答
345
有一个简单的方法（我猜是一个技巧）来记住哪个符号意味着什么。
所有的 Big-O 符号都可以被认为有一个条形图。
当查看 Ω 时，条形图位于底部，因此它是（渐近的）下限。
查看 Θ 时，条形图显然位于中间。所以它是一个（渐近的）紧界。
手写 O 时，通常在顶部完成，然后画一个波浪线。因此 O(n) 是函数的上限。公平地说，这不适用于大多数字体，但它是名称的原始理由。
于 2009-01-23T00:50:42.743 回答
56
一个是大“O”
一个是大Theta
http://en.wikipedia.org/wiki/Big_O_notation
大 O 意味着您的算法将在不超过给定表达式的步骤中执行 (n^2)
Big Omega 意味着您的算法执行的步骤不会少于给定表达式（n^2）
当同一表达式的两个条件都为真时，您可以使用大 theta 表示法....
于 2009-01-22T23:01:36.833 回答
42
我将举一个简单的例子，而不是提供一个理论定义，这里已经很好地总结了：
假设运行时间f(i)为O(1)。下面是一个渐近运行时为Θ(n). 它总是调用函数f(...) n时间。下界和上界都是 n。
for(int i=0; i<n; i++){
f(i);
}
下面的第二个代码片段的渐近运行时间为O(n). f(...) 它在大多数 时候调用该函数n。上限是 n，但下限可能是Ω(1)或Ω(log(n))，具体取决于 内部发生的情况f2(i)。
for(int i=0; i<n; i++){
if( f2(i) ) break;
f(i);
}
于 2012-09-27T19:17:55.620 回答
11
Theta 是指大 O 和 Omega 相同的特殊情况的简写方式。
因此，如果有人声称The Theta is expression q，那么他们也必然声称Big O is expression q并且Omega is expression q。
粗略的类比：
如果： Theta 声称，“那只动物有 5 条腿。” 然后得出这样的结论：Big O 为真（“该动物的腿少于或等于 5 条。”）并且 Omega 为真（“该动物的腿大于或等于 5 条。”）
这只是一个粗略的类比，因为表达式不一定是特定的数字，而是不同数量级的函数，例如 log(n)、n、n^2 等。
于 2015-01-07T06:58:18.080 回答
11
图表可以使之前的答案更容易理解：
Θ-符号 - 相同的顺序 | O 表示法 - 上限
用英语，
请注意，在左侧，有一个上限和一个下限，它们的数量级相同（即g(n)）。忽略常数，如果上限和下限具有相同的数量级，则可以有效地说f(n) = Θ(g(n))或f(n) 处于 g(n) 的大 theta 中。
从右边开始，更简单的例子，它说上界g(n)只是数量级，忽略了常数c（就像所有大 O表示法一样）。
于 2015-05-20T04:17:16.573 回答
6
于 2009-01-22T23:04:04.130 回答
4
使用限制
让我们考虑f(n) > 0一下。考虑到这一点是可以的，因为最快的真实算法至少有一个操作，并在开始后完成它的执行。这将简化微积分，因为我们可以使用值 ( ) 而不是绝对值 ( )。g(n) > 0nf(n)|f(n)|
f(n) = O(g(n))一般的：
f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n)对于
g(n) = n：f(n) 0 ≤ lim ──────── < ∞ n➜∞ n例子：
Expression Value of the limit ------------------------------------------------ n = O(n) 1 1/2*n = O(n) 1/2 2*n = O(n) 2 n+log(n) = O(n) 1 n = O(n*log(n)) 0 n = O(n²) 0 n = O(nⁿ) 0反例：
Expression Value of the limit ------------------------------------------------- n ≠ O(log(n)) ∞ 1/2*n ≠ O(sqrt(n)) ∞ 2*n ≠ O(1) ∞ n+log(n) ≠ O(log(n)) ∞f(n) = Θ(g(n))一般的：
f(n) 0 < lim ──────── < ∞ n➜∞ g(n)对于
g(n) = n：f(n) 0 < lim ──────── < ∞ n➜∞ n例子：
Expression Value of the limit ------------------------------------------------ n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1反例：
Expression Value of the limit ------------------------------------------------- n ≠ Θ(log(n)) ∞ 1/2*n ≠ Θ(sqrt(n)) ∞ 2*n ≠ Θ(1) ∞ n+log(n) ≠ Θ(log(n)) ∞ n ≠ Θ(n*log(n)) 0 n ≠ Θ(n²) 0 n ≠ Θ(nⁿ) 0
于 2016-01-27T08:14:32.980 回答
2
结论：我们认为大O、大θ和大Ω是一回事。
为什么？下面我说一下原因：
首先，我要澄清一个错误的说法，有些人认为我们只关心最坏的时间复杂度，所以我们总是使用大 O 而不是大 θ。我会说这个人在胡说八道。上下界用于描述一个函数，不用于描述时间复杂度。最差时间函数有上下界；最佳时间函数也有其上限和下限。
为了把大O和大θ的关系解释清楚，我先解释一下大O和小o的关系。从定义我们可以很容易的知道小o是大O的一个子集。例如：</p>
T(n)= n^2 + n，我们可以说 T(n)=O(n^2)，T(n)=O(n^3)，T(n)=O(n^4)。但是对于小o，T(n)=o(n^2)不满足小o的定义。所以只有 T(n)=o(n^3), T(n)=o(n^4) 对小 o 是正确的。多余的 T(n)=O(n^2) 是什么？大θ！
一般来说，我们说大O是O(n^2)，很难说T(n)=O(n^3)，T(n)=O(n^4)。为什么？因为我们下意识地把大 O 当作大 θ。
同样，我们也下意识地将大Ω视为大θ。
总之，big O、big θ 和 big Ω 从定义上看不是同一个东西，但在我们的嘴和大脑中它们是同一个东西。
于 2016-11-30T18:22:26.710 回答