python - 为什么分而治之快过reduce解决merge K排序列表

Question

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

这是代码差异:

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

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

我还编写了另一个昂贵的 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 N - log J) 次迭代(N = 元素总数，J = 我们开始的子列表的长度)每次迭代都是 O(N) 因为每个元素只涉及一次合并 -> 总 O(N (log N - log J))

reduce 需要 N/J - 1 个步骤，复杂度为 O(2J)、O(3J)、O(4J)。等等 所以总的复杂度是 O(N^2/J)

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

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