34

我正在学习算法分析。我无法理解 O、Ω 和 Θ 之间的区别。

它们的定义方式如下：

  • f(n) = O(g(n))均值c · g(n)是 的上界f(n)。因此，存在一些常数c，对于足够大 （即，对于某个常数） ，f(n)总是 ≤ 。c · g(n)nn ≥ n0n0
  • f(n) = Ω(g(n))均值c · g(n)是 的下界f(n)。因此，存在一些常数，对于所有c，f(n)总是 ≥ 。c · g(n)n ≥ n0
  • f(n) = Θ(g(n))对于 all 来说，meansc1 · g(n)是 的上界f(n)，c2 · g(n)也是 的下界。因此存在常数和 这样的和。这意味着 对.f(n)n ≥ n0c1c2f(n) ≤ c1 ·g(n)f(n) ≥ c2 ·g(n)g(n)f(n)

我理解的方式是：

  • O(f(n))给出给定函数/算法的最坏情况复杂度。
  • Ω(f(n))给出给定函数/算法的最佳情况复杂度。
  • Θ(f(n))给出给定函数/算法的平均案例复杂度.

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

4

6 回答 6

42

重要的是要记住，符号，无论是 O、Ω 还是 Θ，都表示函数的渐近增长；它本质上与算法本身没有任何关系。所讨论的函数可能是算法的“复杂性”（运行时间），无论是最坏情况、最佳情况还是平均情况，但符号与函数的来源无关。

例如，函数 f(n)=3n 2 +5 是：

  • O(n 2 )，也是O(n 2 log n)、O(n 3 )、O(n 4 )等，但不是O(n)。
  • Ω(n 2 )，也是Ω(n log n)、Ω(n)等，但不是Ω(n 3 )。
  • θ(n 2 )。它甚至不是 Θ(n 2 log n) 或 Θ(n 2 /log n)。

现在，通常考虑的函数是算法的最坏情况复杂度，使用这三个符号中的哪个符号取决于我们想要对它说什么以及我们进行分析的仔细程度。例如，我们可能会观察到，因为有两个嵌套循环，最坏情况下的运行时间最多为O(n 2 )，而不关心对于某些输入是否真的实现了这一点。（通常很明显。）或者，我们可以说排序的最坏情况运行时间是 Ω(n log n)，因为必须有一些输入至少需要 cn(log n)脚步。或者，我们可以查看一个特定的归并排序算法，发现它在最坏情况下最多需要 O(n log n) 步，并且一些输入使它需要 n log n 步，所以最坏情况下的运行时间是 Θ(n log n)。

请注意，在上述所有三个示例中，所分析的运行时间仍然相同（最坏情况）。我们可以改为分析最佳情况或平均情况，但同样，我们使用三种表示法中的哪一种取决于我们想说什么——我们是否要给出一个上限、下限或严格的界限成长同样的功能。

于 2009-12-25T04:43:32.187 回答
36

Θ 表示渐近紧密的上限和下限。

O 表示一个上限，但这个界限可能很紧，也可能不紧。
o 表示不严格的上限。

Ω 表示下限，但这个界限可能很紧，也可能不紧。
ω 表示不紧的下限。

于 2009-12-25T03:55:45.753 回答
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)”。这确实是对符号的滥用，但它明白了重点。

于 2009-12-25T11:00:04.807 回答
4

这些是一些真正可以帮助您的资源：

于 2009-12-25T03:56:28.493 回答
-1

Big-O 表示法通常被称为算法的复杂性，因为它向我们保证，对于较大的 n，该算法不会表现得更差。然而，正如前面正确指出的那样，Big-O 为我们提供了渐近评估，并且当给定特定输入时，我们的算法可能会表现不同。例如，当数组已经排序时，快速排序可以是 O(n^2)。OTOH，在实践中可以通过巧妙的实施来改善渐近情况。

于 2009-12-26T12:47:17.943 回答
-2

最佳情况由 Ω(n) 表示法表示。最坏情况由Ο(n) 表示法表示。平均情况由 Θ(n) 表示法表示。

于 2020-08-27T17:04:29.807 回答