algorithm - 难以理解渐近符号

Question

据我所知和研究，

Big - Oh notation describes the worst case of an algorithm time complexity.

Big - Omega notation describes the best case of an algorithm time complexity.

Big - Theta notation describes the average case of an algorithm time complexity.

Source

然而，最近几天，我看到有人在讨论中说

O for worst case is a "forgivable" misconception. Θ for best is plainwrong. Ω for best is also forgivable. But they remain misconceptions.

The big-O notation can represent any complexity. In fact it candescribe the asymptotic behavior of any function.

我还记得我在大学类(class)中学过前一个。我还是个学生，如果我认识错了，请你解释一下好吗？

Answer 1

Bachmann-Landau 表示法与算法的计算复杂性完全无关。这应该已经很明显了，因为在 1894 年巴赫曼和朗道发明了这种表示法时，计算算法的计算机器的想法并不真正存在。

Bachmann-Landau 表示法通过将函数分组到以大致相同的速率增长的函数集中来描述函数的增长率。 Bachmann-Landau 符号没有说明这些函数的含义。它们只是函数。事实上，它们根本不需要任何意义。

他们的意思是:

• f ∈ ο(g):f 比 g 增长得慢
• f ∈ Ο(g):f 的增长速度并不明显快于 g
• f ∈ Θ(g):f 增长速度与 g 一样快
• f ∈ Ω(g):f 的增长并不明显慢于 g
• f ∈ ω(g):f 比 g 增长得更快

它没有说明 f 或 g 是什么，也没有说明它们的含义。

请注意，实际上有两个 Ω 的相互冲突、不兼容的定义；这里给出的是对计算复杂性理论更有用的一种。另请注意，这些只是非常广泛的直觉，如有疑问，您应该查看定义。

如果需要，您可以使用 Bachmann-Landau 表示法将兔子数量的增长率描述为时间的函数，或者将人类腹部的增长率描述为啤酒的函数。

或者，您可以用它来描述最佳情况步骤复杂度、最坏情况步骤复杂度、平均情况步骤复杂度、预期情况步骤复杂度、摊销步骤复杂度、最佳情况时间复杂度、最坏情况时间算法的复杂度、平均情况时间复杂度、预期情况时间复杂度、摊销时间复杂度、最佳情况空间复杂度、最坏情况空间复杂度、平均情况空间复杂度、预期情况空间复杂度或摊销空间复杂度。