Big-O表示法的定义

Question

我真的想知道真正的定义.我试过看书,却无法理解.

O:Big-O符号最坏的情况.
Θ:Theta表示法的平均情况.
Ω:欧米茄符号最好的情况.

为什么维基百科代表Big-O算法的速度,包括其平均,最佳和最差情况？为什么他们没有取代那些正式的关键词？

Answer 1

O,Θ和Ω不代表最差,平均和最佳情况; 虽然它们有类似的含义.

Big-O表示法f(n)= O(g(n))表示对于大的n值,f比g增长慢(在这种情况下,"n> n ₀ "表示"对于大的n值").这并不意味着g是最坏的情况:g可能比最坏的情况更糟糕(快速排序也是 O(n!)).对于更复杂的算法,正在进行研究以确定最小的Big-O的实际复杂性:原始作者大多发现Big-O上限.

Ω符号表示反向(f增长快于g),这意味着它可能比最佳情况更好(例如,所有算法都是Ω(1)).

存在许多算法,其中没有单个函数g,使得复杂度为O(g)和Ω(g).例如,插入排序具有O(n²)的Big-O下界(意味着您找不到小于n²的任何值)和Ω(n)的Ω上界.

其他算法可以:合并排序是O(n log n)和Ω(n log n).当发生这种情况时,它被写为Θ(n log n),这意味着并非所有算法都具有Θ符号复杂度(并且值得注意的是,具有最坏情况或最佳情况的算法没有一个).

为了摆脱具有极低概率的最坏情况,检查平均情况复杂度是相当普遍的 - 用左侧的标准"f"值替换不同的函数"f _avg ",该函数仅考虑最可能的结果.因此,为了快速排序,f = O(n²)是你能得到的最好的,但是f _avg = O(n log n).

Answer 2

我不确定您在哪里找到这些定义，但我认为它们是不正确的。

\n\n

最好、平均和最差情况都是通常超过输入大小的函数。

\n\n

Big-O、Theta 和 Omega 分别表示任何给定函数的上限、紧限和下限。

\n\n

也就是说，最好的情况有一个大 O、Theta 和 Omega 界限。平均情况和最坏情况也是如此。

\n\n

另请参阅：O 和 \xce\xa9 如何与最坏和最好情况相关？

\n\n

注意：big-O 通常（可以说是错误的）用来表示紧界（而不是 Theta）。

\n\n\n\n

让我们考虑插入排序的例子。

\n\n

最好的情况是它已经排序，在这种情况下，它将花费线性时间，即某个常数的时间。f(n) = k1nk1

\n\n

k1n是 O(n)、\xce\x98(n)、\xce\xa9(n)。根据定义，我们也可以说它是 O(n ² ), O(n ³ ), ... 或 \xce\xa9(1), \xce\xa9(log n), \xce\xa9 (log log n), ...，但通常期望它呈现最紧的界限。

\n\n

最坏和平均情况是和，它们都是 O(n ² )、\xce\x98(n ² )、\xce\xa9(n ² )。g(n) = k2n2h(n) = k3n2

\n\n\n\n

现在您可能会说：这不是很有用，如果它们始终相同，为什么我们需要三个边界？为什么我们不到处使用 Theta 呢？

\n\n

一般来说，你是绝对正确的 - 算法通常仅根据其中一个界限（通常是紧界限）来描述。

\n\n

然而，对于某些算法来说，很难准确地弄清楚紧界是什么，而很容易获得上限和/或下界。计算斐波那契数的未优化算法就是一个这样的例子 - 找到 O(2 ⁿ )的上限和\xce\xa9(1.5 ⁿ )的下限并不难，但是〜的紧界\xce\xb8(1.6 ⁿ ) 计算起来要困难得多。

\n