关于复杂性（如果使用基于比较的排序算法）

Question

众所周知，任何基于比较模型的排序算法都有nlogn的下界，即Omega(nlogn)。 这可以用数学证明。

但众所周知，荷兰国旗问题可以在 O(n) 时间内对 3 个不同的元素（重复使用）进行排序。它也是基于比较模型，但可以在 O(n) 时间内进行排序。 那么我们如何证明基于比较模型的排序下限是合理的，因为荷兰国旗问题有点违反了这一点。

请帮助我理解差异......

谢谢

Answer 1

在我看来，这不是下界的相关“矛盾”，因为它是一种特殊情况（可能的值范围小于元素总数，实际上它是一个常数，3），可以是用于找到比 O(N*logN) 更快的算法，O(N*logN) 是一般基于比较的排序算法的下限（即，您没有关于序列内容的信息）。

通常在N个元素在0..K范围内并且K＜1的情况下。 N 您可以有效地利用非比较排序（例如计数排序）来解决 O(N) 的问题。

Answer 2

边界Omega(n log n) 给出了基于比较的任意元素排序的下限。

荷兰国旗问题考虑的只是没有任意元素，但每个元素只有三个选项的情况。

因此，边界Omega(n log n) 一般情况下适用于该问题，无需额外约束。但是，如果您施加其他约束（例如，每个元素只有三个选项），您很可能能够找到比此限制更好的算法，因为您随后考虑了一个特定情况，其中您也许可以应用其他启发法等。

Answer 3

要点是：荷兰国旗的设置并不是完全有序的。有许多相等的元素，事实上，当您计算不同的对象时，它是一组（最多）大小为 3 的集合。

Omega(n log n) 边界可能仅在对象时才困难>a 和 b 要么 a 要么 b>a 成立（又名：所有对象都是不同的）

事实上，我可以排序O(0)，此时所有对象都必须为 null。

假设至少有两个不同的对象，我相信正确的界限类似于 Omega(n log m)，其中 n 是对象的数量，m 是不同对象的数量（排序不相等）。简单来说，log m是找到输出桶所需的决策数量。一般情况下，如果相等对象的数量较少，则 O(log m)=O(log n)。在荷兰国旗问题中，m=3。

基数排序以不同的方式利用了这一点。它也被认为是线性的。但是，它需要 log m 传递数据，其中 m 是可能不同元素的数量。所以实际上，基数排序也是Omega(n log m)，其中m是它可以识别的对象数量。

Answer 4

荷兰国旗问题比正常排序有一些更基本的数据，它知道存在三个不同的值，如果您查看维基百科页面的算法，它是：

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

事实上，它不使用元素对之间的比较，它只是使用较低/之间的比较中/上界和元素，与普通排序中使用的其他比较方法无关，可以与计数排序进行比较。

Answer 5

荷兰国旗问题更多的是一个划分算法。

这只是排序的第一步。
您可以使用它进行排序（通过一遍又一遍地将其应用于分区），但我猜您最终会得到 Omega(nlogn)。

知道不同值的数量（对于旗帜来说是 3 个）及其值（蓝色、白色、红色）的情况非常罕见。