为什么分而治之比reduce更快来解决merge K排序列表

Question

我正在使用方法5：Merge with Divide And Conquer来解决leetcode中的合并K排序问题。该算法非常快，大约需要100ms。然而，我不明白为什么reduce方法需要更慢的运行时(4000+ms)。

下面是代码diff：

# 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]

如果分治在parallel中运行，我可以理解为什么分治更快，但我认为它应该仍然是线性运行的，对吧？

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

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

这个版本的reduce和divide and conquer的运行时间几乎相同。

有没有reduce不能处理的合并K排序列表测试用例？在“分而治之”中我是不是遗漏了什么？

Answer 1

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

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

reduce需要N/J -1步的复杂度O(2J)，O(3J)，O(4J)。等，因此总复杂度为O(N^2 / J)

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

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