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

有时我看到Θ(n)中间有一个奇怪的Θ符号，有时只是O(n)。只是因为没人知道如何输入这个符号而懒惰打字，还是它有别的意思?

222800 次浏览
小开
最佳答案

简短说明:

如果一个算法是Θ(g(n))，这意味着当n(输入大小)变大时，算法的运行时间与g(n)成正比。

如果一个算法是O(g(n))，这意味着当n变大时，算法的运行时间与g(n)成正比。

通常，当人们谈论O(g(n))时，他们实际上指的是Θ(g(n))，但从技术上讲，这是有区别的。

更多的技术:

O(n)表示上界。Θ(n)表示紧绑定。 Ω(n)为下界

f(x) = Θ(g(x)) iff 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)) iff 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 (ω)符号表示函数的松散上界和松散下界。

总结:

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)

对于更详细的讨论，你可以在维基百科上阅读定义或参考经典教科书，如Cormen等人的算法介绍。

小开

一个是大O

一个是大Theta

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

大O表示算法的执行步数不会超过给定表达式(n^2)

大意味着你的算法执行的步骤不会少于给定表达式(n^2)

对于同一个表达式，当两个条件都为真时，您可以使用大theta符号....

小开

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

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

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

小开

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

所有的大o符号都可以被认为有一个条形。

当查看Ω时，条在底部，所以它是一个(渐近的)下界。

在看Θ的时候，条显然是在中间。所以这是一个(渐近的)紧边界。

当书写O字时，你通常在顶部完成，然后画一圈。因此O(n)是函数的上界。公平地说，这个方法不适用于大多数字体，但它是名称的最初理由。

小开

我不打算提供一个理论定义，这里已经总结得很好了，我将给出一个简单的例子:

假设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和是一样的

因此，如果有人声明The Theta is expression q，那么他们也必然声明Big O is expression q和Omega is expression q。

粗糙的类比:

< p >如果: Theta说，那个动物有5条腿 然后是: 大O是正确的(“那个动物的腿少于或等于5条。”) 而且 Omega为真(“那个动物有超过或等于5条腿。”)

这只是一个粗略的类比，因为表达式不一定是特定的数字，而是不同数量级的函数，如log(n)， n, n²，(等等)。

小开

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

Θ-Notation -同阶| o符号-上限

Θ(n) - Same order O(n) - Upper bound .

在英语中,

在左边，注意有一个上界和下界，它们都是同一个数量级(即g (n))。忽略常量，如果上界和下界具有相同的数量级，则可以有效地说F (n) = Θ(g(n))或F (n)的单位是(g(n))。

从右边开始，更简单的例子，它说上限g (n)只是数量级，忽略常量c(就像所有大魔神符号一样)。

小开

使用限制

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

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

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

    General:

              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
小开

结论:我们认为大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²)不符合小o的定义，所以T(n)=o(n³)，T(n)=o(n²)对小o是正确的，多余的T(n)=o(n²)是什么?太大了θ!

一般来说，我们说大O是O(n²)而不是T(n)=O(n³)T(n)=O(n²)为什么?因为我们潜意识里把大O看成大θ。

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

总而言之，大O、大θ和大Ω从定义上看是不同的，但在我们的口中和大脑中却是一样的。


提交答案