是否可以通过使用乘法将暴力排序中的比较次数从 O(N^2) 减少到 O(N)？

Question

当比较结果赋给整数时：

r1 = A>B
r2 = B>C

我们不需要将 A 与 C 进行比较，因为

r3 = r1 * r2 = 1

仅在以下情况下成立

A>C

对吧？只需 2 次比较和 1 次乘法即可确定 A>C。

继续一个额外的元素：

r4 = C>D
r3 * r4 = A>D
r1 * r4 = not needed as a,b and c,d are independent
r2 * r4 = B>D
...

那么，是否有一种简单的乘法/加法方法可以找到所有元素的比较矩阵，而无需进行比 N 更多的比较？因为使用这样的矩阵，唯一元素数组的排序速度可以比 O(N^2) 比较更快（但包括乘法在内的总操作数仍应保持不变）。这可以建模为矩阵乘法运算（也许可以在 CUDA GPU 的张量核心中加速）？

编辑：根据 derpirscher 的评论，它应该需要的不仅仅是相邻比较。

i: index
i > i+1
i > i+2
i > i+4
i > i+8
i > i+N/2 ----> log2 steps ---> nlogn

Answer 1

在最好的情况下？是的。

如果您测试了正确的比较，您绝对可以用最少的

n-1

比较对列表进行排序。由于大多数排序数据在现实世界中很常见，因此某些排序算法会尝试在数据中查找运行，并使用它来更快地排序。 Timsort 就是一个很好的例子。

但是无法回避斯特林近似法，它说的是

ln(n!) = n ln(n) - n + O(ln(n))

。由于排序算法可能以

n!

方式重新排列列表，因此在大多数情况下它至少需要

Ω(n * log(n))

位（即比较）。这意味着基于比较的算法的平均性能（更不用说最坏情况下的性能）不可能比这更好。

回到你的乘法想法，哪里出了问题？这很简单。虽然乘法可以为您提供有关您实际上并未进行的比较的信息，但平均而言它不会。