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

Question

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

但我们也都知道，荷兰国旗问题可以在O(n)时间内排序3个不同的元素（反复使用）。它也是基于比较模型的，但可以在O(n)时间内排序。

那么我们如何证明基于比较模型的排序的下限，因为荷兰国旗问题似乎违反了这一点。

请帮我理解其中的区别。

谢谢。

- user1057741

Answer 1

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

通常情况下，如果N个元素在0..K范围内，其中K < N，您可以有效地利用非比较排序，如计数排序以O（N）的时间复杂度解决问题。

- Tudor

Answer 2

绑定的Omega（n log n）为任意元素的基于比较的排序提供了下限。

荷兰国旗问题考虑的是每个元素不是任意元素，而是只有三个选项。

因此，对于没有其他约束条件的问题，绑定的Omega(n log n)适用于一般情况。 然而，如果您强制施加其他约束条件（例如，每个元素只有三个选项），则您可能会找到比这个界限更好的算法，因为您可以考虑一个特殊情况，从而可以应用其他启发式方法等。

- phimuemue

Answer 3

问题在于：荷兰国旗集合并非完全有序。实际上，当您计算不同对象时，它是一个大小为3的集合，其中有许多相等的元素。

当对象a和b满足aa（即所有对象都不同）时，Omega(n log n)的限制可能很难实现。

实际上，当所有对象必须为null时，我可以在O(0)内排序。

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

基数排序以不同的方式利用了这一点。它也被认为是线性的。然而，它需要对数据进行log m次遍历，其中m是可能不同元素的数量。因此，实际上，基数排序也是Omega(n log m)，其中m是它可以识别的对象数量。

- Has QUIT--Anony-Mousse

Answer 4

荷兰国旗问题更多地是一个分区算法。

这只是排序的第一步。您可以使用它进行排序（通过反复应用它到分区），但我猜最终会得到Ω（nlogn）。

知道不同值的数量（在旗帜的情况下为3）及其值（蓝色，白色，红色）是非常罕见的情况。

- chb

Answer 5

荷兰国旗问题比普通排序具有更基本的数据，它知道有三个不同的值，如果你查看维基百科页面上的算法，它是：

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;
    }
  }
}

实际上，它并没有使用元素对之间的比较，而是使用下限/中位数/上限和元素之间的比较，这与常规排序中使用的其他比较方法无关，你可以将其与计数排序进行比较。

- user1164667