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

Question

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

time-complexitynotationbig-o

466

有时我看到带有奇怪符号Θ的Θ(n)，有时只是O(n)。这只是因为懒得打字而没有人知道如何键入此符号，还是意味着不同的东西？

- martinus

10

这个问题并不明显，但它是昨天这个问题的重复 https://dev59.com/nnRB5IYBdhLWcg3w7riV。 - Bill the Lizard

可能是下界和紧界的区别？的重复问题。 - Damjan Pavlica

9个回答

362

有一个简单的方法（我猜是一个技巧），可以记住每个符号代表什么意思。

所有的大O符号都可以看作有一条横杠。

当看到Ω时，横杠在底部，因此它是（渐进）下界。

当看到Θ时，横杠显然在中间。因此，它是（渐进）紧密界限。

写O的时候，通常会在顶部完成并画出一个波浪线。因此，O（n）是函数的上界。公正地说，这个方法不适用于大多数字体，但这是名称最初的理由。

- Andrei Krotkov

8

通常我不会在任何问题上回答少于3-4个答案，但这次确实值得一试。感谢分享这个技巧:D - impossible

3

我喜欢这个。但是你能分享一下“它是名称的原始正当性”的来源吗？ - Kelly Bundy

55

一个是大O表示法

一个是大Theta表示法

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

大O意味着您的算法的执行步骤不会超过给定表达式（n^2）

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

当同一表达式同时满足这两个条件时，您可以使用大Theta表示法...

- Kendrick Wilson

23

但这是错误的！随着n越来越大，步骤数上限被绑定为n^2。然而，一个运行在n^2+c步的算法需要超过n^2步，但仍然是O(n^2)。大O符号只描述渐近行为。 - HenryR

1

这并不是一个全面的定义。它只是一个起点...... 因为我们正在讨论当 n 趋近无穷大时的渐进符号。常数 C 成为非因素。 - l_39217_l

1

虽然我喜欢这个答案的简洁性，但应该注意到一个O(n^2)算法可能需要执行1,000,000,000n^2步，这肯定比n^2大得多。一个算法是O(n^2)只意味着它执行不超过kn^2步，其中k是某个正实数。 - MarredCheese

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

- kara deniz

“asymptotic runtime” 是什么意思？ - chopper draw lion4

2

在这个上下文中，“渐近”意味着“当n足够大时”。渐近运行时间为Θ(n)的代码片段的运行时间将随着n的增加而线性增长，例如，运行时间T可以表示为T(n)=a*n+b。对于小的n值（例如n=1或2），这可能不是描述行为的最佳方式——也许您有一些初始化代码需要比f(i)更长时间。 - kara deniz

11

一张图表可以更好地理解之前的答案：

Θ-符号 - 同阶 | O-符号 - 上界

Θ(n) - 同阶 O(n) - 上界

简单地说，左边有一个上界和一个下界都是同阶数量级（即g(n)）。忽略常数，如果上下界同阶数量级，那么可以正确地说f(n)=Θ(g(n))或f(n)属于大theta符号g(n)。

右边是一个更简单的例子，它表示上界g(n)仅仅是数量级，忽略常量c（正如所有的大O符号一样）。

- Ricardo

你把单词和图表搞混了。 - HalfWebDev

@kushalvm，谢谢你的诚实。你能详细解释一下你具体指的是什么吗？为了我的学习和可能会被这个答案弄糊涂的其他人。 :-) - Ricardo

最后一段的最后一行不应该是f(n)是g(n)的Theta吗？ - HalfWebDev

@kushalvm，感谢您澄清。我更改了“倒数第二段”的最后一行文本，以修复我的英语错误。 - Ricardo

请查看有关发音的更多信息。 - Ricardo

显示剩余3条评论

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

- ahnbizcad

6

f(n) 若存在正数 k 使得 f(n)<=k*n，则属于 O(n)。

f(n) 若存在正数 k1、k2 使得 k1*n<=f(n)<=k2*n，则属于 Θ(n)。

关于大 O 符号的维基百科文章

- user54579

1

你错过了一个关键点 - 这些只对所有n > n1成立，即渐近地。 - HenryR

n > n1 的意思是什么？ - chopper draw lion4

5

使用极限

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

`f(n) = O(g(n))`

General:

          f(n)     
0 ≤ lim ──────── < ∞
    n➜∞   g(n)

For g(n) = n:

          f(n)     
0 ≤ lim ──────── < ∞
    n➜∞    n

Examples:

    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

Counterexamples:

    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))`

General:

          f(n)     
0 < lim ──────── < ∞
    n➜∞   g(n)

For g(n) = n:

          f(n)     
0 < lim ──────── < ∞
    n➜∞    n

Examples:

    Expression               Value of the limit
------------------------------------------------
n        = Θ(n)                      1
1/2*n    = Θ(n)                     1/2
2*n      = Θ(n)                      2
n+log(n) = Θ(n)                      1

Counterexamples:

    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

- ROMANIA_engineer

2

结论：我们认为大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看作是大θ。

同样，我们也下意识地把大Ω看作是大θ。

总之，从定义上讲，大O、大θ和大Ω并不是同一件事情，但在我们的口头和脑海中它们是同一件事情。

- haibo cu

为什么这段内容被格式化为引用？它是来自外部来源的引用吗？如果是，应该提供链接或其他标识。如果不是，引用格式应该被移除。 - Mark Amery

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mehrdad Afshari · Accepted Answer

简单解释：

如果一个算法是 Θ(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₂g(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是g的下界（即f(n) = Ω(g(n))，这与g(n) = O(f(n))是完全相同的）。简而言之，

f(x) = Θ(g(x))当且仅当f(x) = O(g(x))且g(x) = O(f(x))

还有小o和小omega (ω)符号表示函数的松弛上界和松弛下界。

总结一下：

f(x) = O(g(x)) (大O符号)意味着 f(x)的增长速度渐进地小于或等于g(x)的增长速度。

f(x) = Ω(g(x)) (大Ω符号)意味着 f(x)的增长速度渐进地大于或等于g(x)的增长速度。

f(x) = o(g(x)) (小o符号)意味着 f(x)的增长速度渐进地小于g(x)的增长速度。

f(x) = ω(g(x)) (小omega符号)意味着 f(x)的增长速度渐进地大于g(x)的增长速度。

f(x) = Θ(g(x)) (theta符号)意味着 f(x)的增长速度渐进地等于g(x)的增长速度。

g(x)的增长率

如需了解更详细的讨论，您可以阅读维基百科上的定义或参考Cormen等人编写的经典教材《算法导论》。