O、Ω和Θ有什么区别？

Question

O、Ω和Θ有什么区别？

34

我正在学习算法分析，但是我对O、Ω和Θ之间的区别感到困惑。

它们的定义如下：

f(n) = O(g(n)) 表示函数 g(n) 对函数 f(n) 是一个上界。因此存在某个常数 c，使得当 n ≥ n0（其中 n0 是某个常数）时，总有 f(n) ≤ c · g(n)。

f(n) = Ω(g(n)) 表示函数 g(n) 对函数 f(n) 是一个下界。因此存在某个常数 c，使得当 n ≥ n0 时，总有 f(n) ≥ c · g(n)。

f(n) = Θ(g(n)) 表示函数 g(n) 同时是函数 f(n) 的上界和下界。也就是说，存在常数 c1 和 c2，使得当 n ≥ n0 时，总有 c2 · g(n) ≤ f(n) ≤ c1 · g(n)。这意味着 g(n) 很好地刻画了 f(n) 的复杂度。

我的理解是：

O(f(n)) 给出了函数/算法的最坏时间复杂度。
Ω(f(n)) 给出了函数/算法的最好时间复杂度。
Θ(f(n)) 给出了函数/算法的平均时间复杂度。

如果我说的不正确，请纠正我。如果是这种情况，每个算法的时间复杂度必须用这三个符号中的所有符号来表示。但我观察到它只用O、Ω或Θ来表示；为什么不是全部三个符号呢？

- Xinus

1

那么，这些答案有帮助还是让你更加困惑了？这里有一些很好的信息，但我认为当你提出问题时你有一个具体的目的。如果你能澄清你的意图，那么某人应该能够提供进一步帮助。 - danben

其实我在读算法书，书中的例子分析了算法的时间复杂度，包括O、Ω和Θ。所以在继续之前，我想确保自己理解得正确。现在看起来清晰一些了，谢谢。 - Xinus

6个回答

36

Θ表示渐进紧密的上下界。

O表示上界，但该上界可能是紧密的也可能不是。
o表示一个不紧密的上界。

Ω表示下界，但该下界可能是紧密的也可能不是。
ω表示一个不紧密的下界。

- Can Berk Güder

6

关于这三个符号的含义，请参见Can Berk Güder的回答。

还要注意的是，它们与最好情况、最坏情况和平均情况完全没有关系。例如，冒泡排序在最好情况下为Θ(n)（因为如果数据已经排序，则只需要n-1次比较），在最坏情况下为Θ(n^2)。如果输入随机洗牌，则其平均情况为Θ(n^2)。因此，该平均情况也是O(n^2)，O(n^3)和O(2^n)。

因此，O、Θ和Ω告诉您它是什么样的界限。它们不告诉您界限是什么。在上下文中，它可能是最好情况、最坏情况、平均情况或算法作为一个整体（所有情况）的界限。

当然，如果一个算法的最好情况是Ω(g)，那么它本身就是Ω(g)。如果它的最坏情况是O(g)，那么它就是O(g)。因此，这里有一个关系。但是，如果它的平均情况是Θ(g)，那么这几乎无法告诉您最好情况和最坏情况的情况。

至于“为什么不全部都用？”。

如果您的函数是Θ(g)，那么它也是O(g)和Ω(g)。因此，提供Θ边界以外的其他边界意义不大。

当您只看到其中一个符号时，通常是因为我们只关心上限或只关心下限。因此，我们说所有比较排序在最坏情况下必须为Ω(n log n)，而冒泡排序在最坏情况下为O(n^2)，但在最好情况下为O(n)，因为我们并不想完全描述时间复杂度，而是在特定的上下文中表达我们关心的边界。

无论如何，大多数人似乎都很懒，不想输入希腊字母。我知道我是。因此，我们只说比较排序“最好为O(n log n)”。这实际上是一种滥用符号，但它传达了要点。

- Steve Jessop

另一个定义也可以，而且正在使用中。我们通常有漂亮的函数g（实际上我们只需要正数），因此我们总是可以通过选择更大的常数c来考虑前几个M（有限多个）。 - ShreevatsaR

真的，但是完整的定义考虑了并非在任何地方都有定义的函数，以及实数函数而不仅仅是整数函数。例如，根据正确的定义，1/x是O(1)，1/(x-1)、1/((x-1)*(x-2))等也是，无需制定特殊条件来解决它们的有限定义域。我猜，如果你不是数学家，这些定义归结为同一件事，原则是“显然我的意思是什么”。但是，在无穷远处的渐近极限（我的定义）和普通极限（你的定义）之间存在差异，差异就在于M的业务。 - Steve Jessop

哦，是的，我已经提到的另一个边缘情况是类似于 f(n) = n + 1，g(n) = n^2。然后，即使显然不存在一个 c，使得 n + 1 <= c * n^2 对于 n = 0，f 仍然是 O(g)。但是看看问题，它确实在定义中指定了“足够大的 n”。所以我怀疑我幻想了它没有，我会删除我的答案中的那一部分。 - Steve Jessop

好的一点是：“足够大的N”定义确实不那么严格……只要它们显然是相同的，这两个定义就是相同的。 :-) （例如，对于离散域，从n≥1开始，g具有正值等）。 - ShreevatsaR

3

这些资源将真正帮助您：

- codaddict

-1

大O符号通常被称为算法的复杂度，因为它向我们保证，对于大的n，算法不会表现得更糟。然而，正如早些时候正确指出的那样，大O给我们提供了渐近评估，当给定某些输入时，我们的算法可能会表现出不同的行为。例如，当数组已经排序时，快速排序可能是O(n^2)。另一方面，在实践中，通过精细的实现，渐近情况可能得到改善。

- D_K

-2

最佳情况用Ω(n)符号表示。最坏情况用Ο(n)符号表示。平均情况用Θ(n)符号表示。

- Jayas P Jacob

这是完全不正确的。 - kaya3

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

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

- ShreevatsaR · Accepted Answer

需要记住的是，符号O、Ω或Θ表示的是一个函数的渐近增长，它本质上与算法无关 per se 。所讨论的函数可能是算法的“复杂度”（运行时间），包括最坏情况、最好情况或平均情况，但这个符号与函数的来源无关。

例如，函数f（n）= 3n²+5是：

O（n²），它也是O（n²log n）、O（n³）、O（n⁴）等，但不是O（n）。
Ω（n²），它也是Ω（n log n）、Ω（n）等，但不是Ω（n³）。
Θ（n²）。甚至不是Θ（n²log n）或Θ（n²/log n）。

通常，我们考虑的函数是算法的最坏情况复杂度，并且使用这三种符号中的哪一种取决于我们想表达什么以及分析得多么仔细。例如，我们可以观察到因为有两个嵌套循环，最坏运行时间最多是O（n²），而不关心是否对于某些输入实际上会达到这个时间复杂度（通常情况下显然会达到）。或者，我们可能会说排序的最坏情况运行时间为Ω（n log n），因为必须存在一些输入，需要至少cn（log n）步才能完成排序。或者，我们可以查看特定的归并排序算法，并发现在最坏情况下它需要最多O（n log n）步并且有些输入会让它花费n log n步，因此最坏情况的运行时间是Θ（n log n）。

请注意，在以上三个示例中，仍然分析的是相同（最坏情况）的运行时间。我们可以分析最佳情况或平均情况，但再次强调，我们使用的这三种符号取决于我们想要表达什么 —— 是否要给出函数增长阶数的上界、下界或紧密界限。