主页 / coding / 问题 / 79014287
Accepted
huseyin tugrul buyukisik
Asked: 2024-09-23 18:51:19 +0800 CST

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

  • 772

当比较结果赋值给整数时：

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
algorithm

2 个回答

  1. Best Answer

    最好的情况是？是的。

    如果您测试了正确的比较，您绝对可以在很少的比较中对列表进行排序。由于大多数排序数据在现实世界中很常见，因此某些排序算法会尝试在数据中n-1查找运行，并使用它来更快地进行排序。Timsort就是一个很好的例子。

    但是斯特林近似法是无法绕过的，它指出ln(n!) = n ln(n) - n + O(ln(n))。由于排序算法可能会以某种方式重新排列列表n!，因此在大多数情况下它至少需要Ω(n * log(n))位（即比较）。这意味着基于比较的算法的平均性能（更不用说最坏情况的性能）不可能比这更好。

    回到你的乘法想法，哪里出了问题？很简单。虽然乘法可以给你提供你实际上没有做的比较的信息，但平均而言它不会。

    • 1

  2. 比较排序至少需要n log(n)比较，这是一个数学证明。所以是的，比较次数可以从 O^2 减少，但不能一直减少到线性。@Btilly 的回答对此提供了很详细的信息。

    但是你也问过Can this be modeled as a matrix-multiplication operation (that could be accelerated in tensor cores of CUDA GPU maybe)?

    比较排序假设有一台机器，比如 CPU。但 CUDA GPU 并非如此，因此 GPU 确实可以绕过限制，一直到O(log n) 时间（深度），尽管它们通常总共使用更多比较。这类排序算法称为排序网络。为任何给定设计一个最佳排序网络n非常困难，但有简单的算法可以生成深度（时间）为的排序网络O(log(n)^2)。虽然很有趣，但通常协调核心的开销以及 GPU 的 I/O 几乎总是比在 CPU 上执行这些排序慢。

    • 1

相关问题