时间戳

首页 > 解决方案 > 如何设计一个高效的排序对手？

java - 如何设计一个高效的排序对手？

问题描述

理论上，我们知道基于比较的排序算法的比较次数是 ceil(lg(n!))，其中 lg 代表以 2 为底的对数。

我们可以建立一个对手，我们通过计算偏序的线性扩展数来选择排序，如果小于或大于这两种情况。无论哪个具有更高的线性扩展，都选择该路径。（这会自动处理不一致，因为如果回复在一侧不一致，它将为零，其他将与前一个相同）

然而，这样的对手效率不高，因为计算部分顺序的线性扩展数是#P-complete。

另一种选择是使用更简单的多项式时间对手，它可以：

  1. a > b 如果 a 从未输过，并且 b 至少输过一次。
  2. a > b 如果双方都不败，并且 a 的胜场数比 b 多。
  3. a > b 如果偏序强制 a > b
  4. a < b 如果偏序强制 a < b
  5. 选择任何其他。

这个对手取自计算机编程艺术，第 3 卷，第二版，第 209 页。它非常适用于查找第二大元素等问题，因为它强制进行 n + ceil(lg(n)) - 2 次比较。不幸的是，它并没有强制信息理论界进行排序。即使我添加了更多启发式方法，例如支配计数（大于的值的数量）来比较而不是随机选择顺序，这仍然是正确的。

我知道它不会强制，因为 Java 8 中的 Collections.sort() 在下限为 75 时对 74 次比较中的 23 个元素数组进行排序。源代码显示，对于所有小于 23 的数字，它能够强制下限，对于 100 个数字，sort() 在下限为 525 时设法进行 in506 比较。

是否存在一个多项式时间有效的对手，它迫使排序算法至少使用信息论界限？

标签： javaalgorithmsortingcomparison

解决方案

有一个“可能近似成功”的多项式时间对手，它使用随机化（例如）强制 ceil(lg(n!) - n -100 ) 以至少 1 - n -100的概率进行比较。

关键思想是，虽然计算线性扩展的数量很困难，但采样均匀随机扩展很容易（至少是多项式时间），因此我们可以对 a < b 的扩展数量进行大概正确的估计与 a > b 相比。显然，如果计数足够接近，我们无法判断哪个更有可能，但是通过获取足够的样本（但仍然是多项式数），我们可以证明使用 Hoeffding 界，其概率至少为 1 - n -102，对手选择的结果至少与线性扩展的 1/2 - n -102部分一致。我们可以将这些错误的累积效应限制在 n -100范围内。

推荐阅读