能否通过乘法将暴力排序的比较次数从O(N²)降至O(N)？

核心推导思路 #

将元素间的比较结果赋值为整数：

r1 = A>B
r2 = B>C

无需直接比较A与C，因为仅当A>C时，r3 = r1 * r2 = 1成立——仅用2次比较加1次乘法即可判断A>C。

当新增元素D时：

r4 = C>D
r3 * r4 = A>D
r2 * r4 = B>D

其中r1 * r4无计算必要，因为A、B与C、D的比较关系相互独立。

延伸问题 #

1. 是否存在简单的乘加方式，仅通过不超过N次比较就能生成所有元素的比较矩阵？若可行，唯一元素数组的排序比较次数就能快于O(N²)（总操作数包含乘法）。
2. 能否将该过程建模为矩阵乘法，利用CUDA GPU的张量核实现加速？

补充修正 #

根据derpirscher的评论，仅做相邻元素比较并不足够，需要进行以下间隔递增的比较操作：

i: 索引
i > i+1
i > i+2
i > i+4
i > i+8
i > i+N/2 ----> log2 步长 ----> 总复杂度nlogn

内容的提问来源于stack exchange，提问作者huseyin tugrul buyukisik