以下程序的時間複雜度是多少？ 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）是否正確？

回答

相關問題