4

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

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

请帮助我理解其中的区别......

谢谢

4

5 回答 5

3

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

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

于 2012-01-23T11:23:34.870 回答
2

该界限为任意元素Omega(n log n)的基于比较的排序提供了一个下限。

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

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

于 2012-01-23T11:26:26.960 回答
1

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

界限可能只有在对象和其中一个或持有Omega(n log n)时才很难（又名：所有对象都是不同的）aba<bb>a

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

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

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

于 2012-01-23T11:31:43.860 回答
0

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

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

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

于 2012-01-23T11:38:22.920 回答
0

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

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

实际上它并没有使用元素对之间的比较，它只是使用了下/中/上限与元素之间的比较，这与普通排序中使用的其他比较方法无关，您可以将其与计数排序进行比较。

于 2012-01-23T11:30:50.100 回答