这是从名为Intro to Algorithms的流行书中获得的 . 作者指出，在最坏的情况下，任何比较排序算法都需要Ω（nlgn）比较 . 以冒泡排序算法为例，在最坏的情况下，我们有一个上限O（n ^ 2） . Omega表示较低或最小的边界，因此最坏情况的下限也不是Ω（n ^ 2）？如果气泡排序具有下限，例如建议的Ω（nlgn），而不是最差情况下的n ^ 2？在最糟糕的情况下，性能冒泡排序不能占用至少nlgn .
为了略微过度简化*，当我们谈论算法问题的下限时，我们对最坏情况下最佳算法的作用感兴趣 . 最好的基于比较的排序算法（例如，mergesort）在最坏的情况下使用大约n log n比较，因此排序的下限被引用为Omega（n log n） . 不是最好的算法，例如冒泡排序，可能比最坏情况下的最佳算法更糟糕 . 在最好的情况下，它们可能比最好的算法做得更好 . 这些事实都不与排序的下限不一致 .
*可能没有一个最好的算法 .
作者说任何算法：在最坏的情况下，没有算法比 Ω(N Log(N)) 做得更好 .
Ω(N Log(N))
原因很容易理解：任何基于比较的排序算法都是二元决策树（if-then-else的长动态序列） . 由于算法必须能够处理数据的任何排列，因此它必须能够以不同方式置换所有 N! 个案例，并且树必须至少具有多个叶子 . 因此决策树的高度，即最坏情况的复杂性，至少是 Lg(N!)=Ω(N.Log(N)) .
N!
Lg(N!)=Ω(N.Log(N))
当决策树很好地 balancer （Heapsort）时，高度也是 O(N.Log(N)) .
O(N.Log(N))
当决策树强烈失衡（Bubblesort）时，高度可以变为 O(N²) .
O(N²)
Addendum ：
由于 Ω 表示下限，因此任何下限都是有效的 . 因此，冒泡排序的最坏情况是 Θ(N²) ，它也是 Ω(N²) ， Ω(N.Log(N)) ， Ω(N) ， Ω(Log N) ， Ω(1) ......
Ω
Θ(N²)
Ω(N²)
Ω(N.Log(N))
Ω(N)
Ω(Log N)
Ω(1)
你需要关注"at least"的含义，用 Ω 表示 .
“在最坏的情况下，冒泡排序需要 Ω(nlg(n)) 比较”不是一个错误的声明，因为它需要至少 knlg(n) 比较一些常量 k .
Ω(nlg(n))
knlg(n)
k
是的，我们知道在最坏的情况下，冒泡排序需要 Ω(n^2) . 但是，这并不会使上述声明为假 . 因此，作者声称是正确的 .
Ω(n^2)
这是一个例子，希望澄清情况：
“无论我多累，我至少可以做50次俯卧撑”
所以知道，以下声明是假的吗？
“无论我有多累，我都可以做至少20次俯卧撑”
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.8/d3.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/knockout/2.3.0/knockout-min.js"></script> <script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.2.23/angular.min.js"></script>
4 回答
为了略微过度简化*，当我们谈论算法问题的下限时，我们对最坏情况下最佳算法的作用感兴趣 . 最好的基于比较的排序算法（例如，mergesort）在最坏的情况下使用大约n log n比较，因此排序的下限被引用为Omega（n log n） . 不是最好的算法，例如冒泡排序，可能比最坏情况下的最佳算法更糟糕 . 在最好的情况下，它们可能比最好的算法做得更好 . 这些事实都不与排序的下限不一致 .
*可能没有一个最好的算法 .
作者说任何算法：在最坏的情况下，没有算法比
Ω(N Log(N))做得更好 .原因很容易理解：任何基于比较的排序算法都是二元决策树（if-then-else的长动态序列） . 由于算法必须能够处理数据的任何排列，因此它必须能够以不同方式置换所有
N!个案例，并且树必须至少具有多个叶子 . 因此决策树的高度，即最坏情况的复杂性，至少是Lg(N!)=Ω(N.Log(N)).当决策树很好地 balancer （Heapsort）时，高度也是
O(N.Log(N)).当决策树强烈失衡（Bubblesort）时，高度可以变为
O(N²).Addendum ：
由于
Ω表示下限，因此任何下限都是有效的 . 因此，冒泡排序的最坏情况是Θ(N²)，它也是Ω(N²)，Ω(N.Log(N))，Ω(N)，Ω(Log N)，Ω(1)......你需要关注"at least"的含义，用
Ω表示 .“在最坏的情况下，冒泡排序需要
Ω(nlg(n))比较”不是一个错误的声明，因为它需要至少knlg(n)比较一些常量k.是的，我们知道在最坏的情况下，冒泡排序需要
Ω(n^2). 但是，这并不会使上述声明为假 . 因此，作者声称是正确的 .这是一个例子，希望澄清情况：
“无论我多累，我至少可以做50次俯卧撑”
所以知道，以下声明是假的吗？
“无论我有多累，我都可以做至少20次俯卧撑”