以下程序的时间复杂度是多少？ O（log n）是否正确？

查找数组中所有偶数的和。递归程序来获得总和。这个程序的时间复杂度是多少，我如何分析它？以下程序的时间复杂度是多少？ O（log n）是否正确？

def sumEven(arr): 
    if len(arr) == 0: 
     return 0 
    if len(arr) == 1: 
     if arr[0]%2 == 0: 
      return arr[0] 
     else: 
      return 0 
    else: 
     mp = len(arr)//2 
     return sumEven(arr[0:mp]) + sumEven(arr[mp:])

来源

2017-02-09 Aravind

该代码将数组中的偶数相加。 O（log n）算法只能查看数组中的O（log n）个条目。 –

可能重复[大O，你如何计算/近似它？]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） –

它仍然O(n)（n/2如果你想更精确）。你在每一步都将工作分解成一半，但是当你走上链时必须重新组合。如果不执行#even值，则不能添加所有的偶数值 - 最少为1次加法运算。这只会提高任何给定的加法运算符大小相等的可能性，其中循环直接会使一个累加器操作数不断增长，因为源操作数保持相同的大小。

忽略均匀度元素，可以这样总结数组中的所有数字。如果您有八个元素，您可以将偶数元素添加到奇数（四个操作，留下四个元素），然后将偶数结果添加到奇数结果（两个操作，留下两个元素），然后将这两个剩余值一起添加（一个操作，留下答案）。您执行了4 + 2 + 1 == 7操作来添加8个值。你只需要完成相同的编号：

elems = [1,2,3,4,5,6,7,8] 

accumulator = elems[0] 
# Loop runs seven times, for all but first element, so seven additions performed 
for operand in elems[1:]: # Ignore the slice cost here; avoidable, but irrelevant 
    accumulator += operand

来源

2017-02-09 03:45:58 ShadowRanger

以下程序的时间复杂度是多少？ O（log n）是否正确？

回答

相关问题