最佳方式

Question

存在使用環路例如加入整數標準方式，

sum =0; 
for(int i =0;i<arraySize;i++){ 
    sum+=array[i]; 
} 

上述邏輯的時間複雜度是O（n ），但是如果n非常大（考慮10^10），那麼計算需要更多時間。所以，請給我任何解決方案，以小於O（n）的時間複雜度工作。

Answer 1

您可以通過始終保持數組總和的記錄來完成此操作。從一個空數組和一個空變量sum開始。然後，每當你添加一個項目到數組，相應地更新總和。

有兩個主要操作會影響數組數組的總和：向數組中添加一個新數字，並從數組中刪除一個數字。添加時，和會變成添加到新號碼的前一個總和。因此只需將新號碼的值添加到sum變量中即可。當刪除一個項目時，總和變成總和減去被刪除的數字。因此，從sum中減去正在刪除的項目的值。更多的操作可以執行，但它們都基於這兩個。

因此，您可以實施insert,pop和replace 方法或函數來爲您抽象該作品。

因此，無論何時您添加或刪除一個項目，您都會通過一些O（1）算法重新計算總和。但是你可以訪問O（1）時間的總和，因爲總和在一個變量中。這當然要求你不要直接改變數組的值而不使用你的函數/方法。

不幸的是，我不太瞭解C和Java，並不足以提供實現。我希望從數據結構中勾勒出來有助於實現這一點。

編輯︰這是一個Python實現來顯示的概念。希望你能從中獲得核心。

class ArraySum: 
    ''' contains an array of numbers and a representation of the 
     sum, which is updated in each insert/pop/replace operation ''' 
    def __init__(self): 
     self._data = [] 
     self.sum = 0 

    def append(self, elem): 
    ''' add an item to the array''' 
     self.sum += elem # update sum 
     self._data.append(elem) # add to array 

    def pop(self, i=None): 
    ''' remove the item at index i of the array''' 
     if i is None: 
      i = len(self._data) 
     self.sum -= self._data[i] 
     return self._data.pop(i) 

    def replace(self, i, elem): 
    ''' replace the item at i by a new element''' 
     self.sum -= self._data[i] 
     self.sum += elem 
     self._data[i] = elem 

if __name__ == '__main__': 
    a = ArraySum() 

    a.append(4) 
    print(a.sum) # sum = 0 + 4 
    a.append(8) 
    print(a.sum) # sum = sum + 8 
    a.pop(1) 
    print(a.sum) # sum = sum - 8 
    a.replace(0, 1) 
    print(a.sum) # sum = sum - 4 + 1 

Answer 2

考慮塊

sum =0; 
for(int i =0;i<arraySize; i = i + 5){ 
    sum+=array[i]; 
    sum+=array[i+1]; 
    sum+=array[i+2]; 
    sum+=array[i+3]; 
    sum+=array[i+4]; 
} 

當然循環通過你需要正確地檢查出界。

在這個平凡的例子我懷疑有要作出的任何收益