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

Question

有时我会看到 θ(n) 带有奇怪的 θ 符号，中间有一些东西，有时只是 O(n)。 这只是因为没有人知道如何输入这个符号而懒得打字，还是它有不同的含义？

Answer 1

简短说明：

如果算法的大小为 θ(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²), O( n^1000000), O(2ⁿ), ...但是 θ(n) 算法不是 θ(n² ）。

事实上，由于 f(n) = θ(g(n)) 意味着 n 值足够大，因此 f(n) 可以限制在 c₁g(n) 和 c _内2g(n) 对于 c₁ 和 c₂ 的某些值，即 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 是 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 (< code>ω) 表示函数的松散上限和松散下界的符号。

总结一下：

f(x) = O(g(x)) (big-oh) 意味着
f(x) 的增长率为
渐近小于或等于
到到g(x)的增长率。

f(x) = Ω(g(x)) （大欧米伽）意味着
f(x) 的增长率为
渐近大于或
等于g(x)

的增长率

f(x) = o(g(x))（小哦）意味着
f(x) 的增长率为
渐近小于
g(x) 的增长率。

f(x) = ω(g(x)) （小欧米伽）意味着
f(x) 的增长率为
渐近大于
g(x)

的增长率

f(x) = θ(g(x)) (theta) 意味着
f(x) 的增长率为
渐近等于
g(x)

的增长率

如需更详细的讨论，您可以阅读定义在维基百科上或查阅经典教科书，例如 Cormen 等人的《算法导论》。

Answer 2

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

所有 Big-O 表示法都可以被视为有一个小节。

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

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

手写 O 时，您通常在顶部完成，并画一条曲线。 因此 O(n) 是函数的上限。 公平地说，这个字体不适用于大多数字体，但它是这些名称的最初理由。

Answer 3

一个是大“O”，

一个是大西塔

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

Big O 意味着您的算法执行的步骤不会多于给定表达式 (n^2)

Big Omega 表示您的算法执行的步骤不会少于给定表达式 (n^2)

当两个条件都为 true 时同样的表达式，你可以使用大theta符号......

Answer 4

我不会提供理论定义（这里已经对其进行了精美的总结），而是给出一个简单的示例：

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

Answer 5

Theta 是指特殊情况的简写方式，其中
大O和欧米茄是一样的。

因此，如果有人声称 Theta 是表达式 q，那么他们也必然声称 Big O 是表达式 q，而 Omega 是表达式 q。

---

粗略的类比：

如果：
Theta 声称：“那只动物有 5 条腿。”
那么可以得出：
大 O 是正确的（“该动物的腿少于或等于 5 条。”）
和
Omega 是正确的（“该动物有超过或等于 5 条腿。”）

这只是一个粗略的类比，因为表达式不一定是具体数字，而是不同数量级的函数，例如 log(n)、n、 n^2，（等等）。

Answer 6

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

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

在英语中，

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

从右边开始，这是一个更简单的例子，它表示上限 g(n) 只是数量级，并忽略常数 c （就像所有 g(n) >big O 符号可以）。

Answer 7

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

如果存在正 k1、k2 作为 ，f(n) 属于 θ(n) >k1*n<=f(n)<=k2*n

关于 Big 的维基百科文章O 表示法

Answer 8

使用限制

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

1. 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)) ∞ 
     

2. f(n) = θ(g(n))

   一般：

   <前><代码> f(n)
   0＜ 林 ──────── < 无穷大
   n➜∞ g(n)

   对于g(n) = n：

   <前><代码> f(n)
   0＜ 林 ──────── < 无穷大
   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 
     

Answer 9

结论：我们将大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的定义。 所以对于小 o，T(n)=o(n^3)、T(n)=o(n^4) 是正确的。 冗余的T(n)=O(n^2)是什么？ θ 太大了！

一般我们说大O就是O(n^2)，很难说T(n)=O(n^3)，T(n)=O(n^4)。 为什么？ 因为我们潜意识里把大O当作大θ。

同样，我们潜意识里也会将大Ω视为大θ。

总而言之，大O、大θ、大Ω从定义上看并不是一回事，但在我们的嘴里和大脑里却是同一件事。