分而治之数组求和或基于循环的数组求和？

Question

我尝试使用这两种算法对数组求和：

基于分而治之
基于朴素循环的算法

代码如下：

# Summation divide and conquer
def summation(array,left,right):
   if left == right:
       return array[left]
   else:
       if left == right-1:
           return array[left] + array[right]
       else:
           mid  = left + (right-left)//2
           left_hand = summation(array,left,mid)
           right_hand = summation(array,mid+1,right)
           return left_hand + right_hand

还有..

# Loop summation
def summation_normal(array):
   sums = 0
   for i in range(len(array)):
       sums += array[i]
   return sums

上述两种算法都可以正常工作并且渐近都是 O(n)。

但我无法确定哪一个更快。请帮助

Answer 1

我会做这样的事情：

a = np.random.randint(0, 1000, 10000)
%timeit summation(a, 0, len(a)-1)
3.59 ms ± 81 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

输出：

%timeit summation_normal(a)
1.29 ms ± 7.45 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

请记住，这些时间在很大程度上取决于处理器中正在进行的活动以及其他几个因素。

显然 summation_normal 是这里的赢家。

Answer 2

两种算法中对数组值执行的加法次数（几乎！）相同，但递归算法的开销更大，因此运行会稍微慢一些。

您可以想象递归算法通过二叉树，获取两个子节点的值并将它们相加到它们的父节点中。因此（数组值的）加法数对应于该树的内部节点数。

现在看一个由 2 个元素组成的短数组（索引为 0 和 1）：

       +
      / \
     0   1

加号表示递归算法中唯一发生的加法。现在想象一个元素被添加到数组中。这意味着其中一个叶节点成为两个叶节点的父节点（添加了一个叶节点）。例如：

所以现在还需要进行一项加法：多了一个内节点。很容易看出，在这个结构中再增加一个数组元素，内部节点的个数就增加了1，所以还会多一个。

同样，在树表示中，叶节点表示数组值，内部节点表示所做的中间总和。

二叉树的叶子数总是比内部节点数多一个。因此，涉及数组值的加法次数为 n-1。这比迭代解少一个，因为第一个（也是额外的）加法是 0 + array[0]。您可以通过从 array[0] 开始并从索引 1 开始循环来改进它。如果您这样做，两种算法都将执行涉及数组值的 n-1 加法。

显然递归算法有更多的"housekeeping"要做：计算中间索引，使用堆栈传递参数，...等等，所以它会慢一点，但不会有不同的时间复杂性。

分而治之数组求和或基于循环的数组求和？

Divide and Conquer array summation or Loop based array Summation?

python

divide-and-conquer