Big-O 符号定义

Question

我真的很想知道真正的定义。我试图读一本书，但无法理解。

O:Big-O 表示法最坏的情况。
Θ:Theta 符号平均情况。
Ω:Omega 表示法的最佳情况。

为什么维基百科只代表 Big-O 中的算法速度，包括其平均、最佳和最坏情况？他们怎么没有用那些正式的关键字来代替？

Answer 1

O, Θ 和 Ω 不代表最坏、平均和最好的情况；虽然它们有相似的含义。

Big-O 表示法 f(n) = O(g(n)) 表示对于较大的 n 值，f 的增长速度比 g 慢(“n > n0”在此上下文中表示“对于较大的 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)，这意味着并非所有算法都具有 Θ 符号复杂度(特别是，最坏情况或最好情况的算法没有一个)。

为了摆脱概率非常低的最坏情况，检查平均情况的复杂性是相当普遍的——用一个不同的函数“favg”替换左侧的标准“f”值，该函数只考虑最可能的结果。所以，对于快速排序，f = O(n²) 是你能得到的最好结果，但是 favg = O(n log n)。