不同渐近符号之间有什么区别？

2018-06-14 02:42:04

我在渐近符号中非常困惑。据我所知，Big-O符号表示最糟糕的演员，欧米茄是最好的情况下，theta是平均情况。然而，我总是看到Big O在任何地方都被使用，即使是最好的情况。例如，在以下链接中，请参阅提到不同排序算法的时间复杂度的表格 -

https://en.wikipedia.org/wiki/Best,_worst_and_average_case

无论是最佳情况，最差情况还是平均情况，表格中的任何地方都使用大O标记。那么其他两种符号的用法是什么？我们在哪里使用它？

据我所知，Big-O符号表示最糟糕的演员，欧米茄是最好的情况下，theta是平均情况。

他们不是。 Omicron是用于（渐近的）上界，omega用于下界，θ用于紧界，这是一个上界和一个下界。如果算法的下限和上限不同，那么复杂度就不能用theta符号来表示。

上界，下界，紧界的概念与最佳，平均，最坏情况的概念正交。您可以分析每个案例的上限，并且可以分析最坏情况的不同界限（以及上述任何其他组合）。

渐近边界总是与表达式中的一组变量相关。例如， O(n)与n 。最好的，平均的和最坏的情况出现在其他所有事物中，但是n 。例如，如果n是元素的数量，那么不同的情况可能会从元素的顺序或唯一元素的数量或值的分布中出现。

然而，我总是看到Big O在任何地方都被使用，即使是最好的情况。

这是因为在描述算法时，上限几乎总是最重要和最有趣的。我们很少关心下限。就像我们很少关心最好的情况一样。

在描述已被证明具有特殊复杂性的问题时 ，下限有时很有用。例如，已经证明，所有通用比较排序算法的最坏情况复杂度是Ω(n log n) 。如果排序算法也是O(n log n) ，那么根据定义，它也是Θ(n log n) 。

O(...)基本上意味着“不比......慢（太慢）”。
它可以用于所有三种情况（“最坏的情况不会慢于”，“最好的情况不会慢于”等等）。

欧米茄是对手：你可以说，有些事情不会比... ...快得多。再次，它可以用于所有三种情况。与O(...)相比，这并不重要，因为告诉某人“我确定我的程序不比你的速度快”是没有什么值得自豪的。

Theta是一个组合：它“（或多或少）与......一样快，而不仅仅是更慢/更快。

大O是上限，而不是最坏的情况！没有特别针对最坏情况/最好情况的符号。你所说的所有例子都有Big O，因为它们都是由给定值限定的上限。我建议你再看看你学习基础知识的书，因为这对理解非常重要:)

编辑：回答你的疑问 - 因为通常情况下，我们感到困扰于我们的最高性能，即当我们说，我们的算法在最佳情况下以O（logn）执行时，我们知道它的性能不会比对数时间差在给定的情况下。这是我们试图减少的上限，因此我们通常会提到大的O来比较算法。（并不是说我们从不提及其他两个）

链接地址: http://www.djcxy.com/p/40181.html