Θ(n) 和 O(n) 有什么区别？

简短说明：

如果一个算法是 Θ(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(n2)、O(n1000000)、O(2n)，...但是 Θ(n) 算法不是 Θ(n2)。

事实上，由于 f(n) = Θ(g(n)) 意味着对于足够大的 n 值，对于 c1 和 c2 的某些值，f(n) 可以绑定在 c1g(n) 和 c2g(n) 内，即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) 的增长率

如需更详细的讨论，您可以read the definition on Wikipedia或查阅经典教科书，例如 Cormen 等人的算法介绍。

---

有一个简单的方法（我猜是一个技巧）来记住哪个符号意味着什么。

所有的 Big-O 符号都可以被认为有一个条形图。

当查看 Ω 时，条形图位于底部，因此它是（渐近的）下限。

查看 Θ 时，条形图显然位于中间。所以它是一个（渐近的）紧界。

手写 O 时，通常在顶部完成，然后画一个波浪线。因此 O(n) 是函数的上限。公平地说，这不适用于大多数字体，但它是名称的原始理由。

---

一个是大“O”

一个是大Theta

http://en.wikipedia.org/wiki/Big_O_notation

大 O 意味着您的算法将在不超过给定表达式的步骤中执行 (n^2)

Big Omega 意味着您的算法执行的步骤不会少于给定表达式（n^2）

当同一表达式的两个条件都为真时，您可以使用大 theta 表示法....

---

我将举一个简单的例子，而不是提供一个理论定义，这里已经很好地总结了：

假设 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);
}

---

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 等。

---

chart 可以使前面的答案更容易理解：

Θ-符号 - 相同的顺序 | O 表示法 - 上限

https://i.stack.imgur.com/4U2AF.gif

用英语讲，

请注意，在左侧，有一个上限和一个下限，它们的数量级相同（即 g(n) ）。忽略常数，如果上限和下限具有相同的数量级，则可以有效地说 f(n) = Θ(g(n)) 或 f(n) 在 g(n) 的大 theta 中。

从右边开始，更简单的例子，它说上界 g(n) 只是数量级并且忽略了常数 c（就像所有大 O 表示法一样）。

---

如果存在正 k 作为 f(n)<=k*n，则 f(n) 属于 O(n)

如果存在正 k1，则 f(n) 属于 Θ(n)，k2 为 k1*n<=f(n)<=k2*n

Wikipedia article on Big O Notation

---

使用限制

让我们考虑所有 n 的 f(n) > 0 和 g(n) > 0。考虑到这一点是可以的，因为最快的真实算法至少有一个操作，并在开始后完成它的执行。这将简化计算，因为我们可以使用值 (f(n)) 而不是绝对值 (|f(n)|)。

f(n) = O(g(n)) 一般：f(n) 0 ≤ lim ──────── < ∞ n➜∞ g(n) 对于 g(n) = n：f(n) 0 ≤ lim ──────── < ∞ n➜∞ n 示例：表达式 极限值 -------------------------- ---------------------- 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 反例：表达式 极限值---- --------------------------------------------- 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 例子：极限的表达式值--------------------------------- --------------- n = Θ(n) 1 1/2*n = Θ(n) 1/2 2*n = Θ(n) 2 n+log(n) = Θ(n) 1 反例：极限的表达式值------------------------- ------------ 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

---

结论：我们认为大O、大θ和大Ω是一回事。为什么？我将原因如下：首先，我要澄清一个错误的说法，有些人认为我们只关心最坏的时间复杂度，所以我们总是使用大O而不是大θ。我会说这个人在胡说八道。上下界用于描述一个函数，不用于描述时间复杂度。最差时间函数有上下界；最佳时间函数也有其上限和下限。为了把大O和大θ的关系解释清楚，我先解释一下大O和小o的关系。从定义我们可以很容易地知道小o是大o的一个子集。例如：

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 Ω 从定义上看不是同一个东西，但在我们的嘴和大脑中它们是同一个东西。

---