为什么分而治之比归并K排序表更快

Question

我正在使用方法5:合并和分治来解决leetcode中的合并K排序问题。该算法速度非常快，大约需要100毫秒。但是，我不明白为什么reduce方法的运行时间要慢得多（4000毫秒）。

这里是代码差异：

# reduce
import functools
return functools.reduce(_mergeTwoLists, lists)

# divide and conquer
step = 1
while step < num:
   for i in range(0, num - step, step * 2):
       lists[i] = _mergeTwoLists(lists[i], lists[i + step])
   step *= 2
   return lists[0]

如果分而治之是在并行中运行，我可以理解分而治之为什么更快，但我想它应该仍然是线性运行的，对吗？

我还写了另一个昂贵的版本的合并来测试差异：

  def add(a, b):
       tmp = 0
       for i in range(1, 5000):
           tmp += i
       return a + b 

这个减少和分治的版本运行时间几乎相同。

是否存在reduce无法处理的合并K排序列表测试用例？在《分而治之》中，我缺少了什么吗？

Answer 1

这两种方法的复杂性是不同的。二次合并是O（mn），其中m和n是两个列表的长度。

分而治之需要O（log N-log J）次迭代（N=元素总数，J=我们开始的子列表长度），每次迭代都是O（N），因为每个元素正好涉及一个合并-

reduce需要N/J-1步的复杂度O（2J），O（3J），O（4J）。所以总的复杂度是O（N^2/J）

请注意，在这两种情况下，两次合并的总数是相同的，不同之处在于分治合并的平均成本更低。

这与您的观察一致，即用加法替换二重合并会产生大致相等的运行时间，因为加法的成本基本上与操作数无关（我想你是在加数，而不是列表？）尤其是当它被燃烧时间循环淹没时。