众所周知，任何基于比较模型的排序算法都有 nlogn 的下界，即 Omega(nlogn)。 这可以从数学上证明。
但众所周知，荷兰国旗问题可以在 O(n) 时间内对 3 个不同的元素(重复使用)进行排序。它也是基于比较模型，但可以在 O(n) 时间内排序。 那么我们如何证明基于比较模型的排序下限是合理的，因为荷兰国旗问题有点违反了这一点。
请帮助我理解其中的区别......
谢谢
最佳答案
在我看来，这不是下界的相关“矛盾”，因为它是一个特例(取值的可能范围小于元素总数，实际上是一个常数，3)可以利用它找到比 O(N*logN) 更快的算法，O(N*logN) 是一般基于比较的排序算法的下限(即，您没有关于序列内容的信息)。
通常在 N 个元素在 0..K 范围内且 K < N 的情况下，您可以有效地利用非比较排序(如计数排序)来解决 O(N) 中的问题。
关于algorithm - 关于复杂性(如果使用基于比较的排序算法)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8970747/