添加n個數字的時間複雜度是多少

Question

如果我必須添加像數字1,12,14,71,83,21那樣的任意數字......那麼這個操作的時間複雜度是多少？

我知道添加兩個數字是O（1），但是如何處理n個數字的列表。假設我正在使用盡可能好的數據結構來存儲這些數據結構，那麼可以對流程產生任何影響！

在此先感謝！

Answer 1

這將是O(N)。例如，在僞代碼，而列表中包含的數字：

while(list[i] != end) { //n in the size of the list, so O(N) 
    sum += list[i]; //O(1) 
    i++; //O(1) 
} 

不管結構是什麼，它會永遠是O(N)，因爲你必須檢查（添加）每個元素。

Answer 2

添加2個數字是O（1）由於操作本身是恆定時間並且輸入是固定的。無論輸入如何，操作都將節省時間。

移動到項目的集合，操作仍然是恆定的時間，但現在它正在多次完成。輸入大小（N）越大，需要的時間越長，並且增長率將是線性的 - 對於輸入中的每個額外項目，操作將需要多一個週期。

因此，時間複雜度爲O（N）。

Answer 3

這是O(N)。每個數據點必須至少被擊中一次。

但是，假設您的問題是實用的而不是理論上的：如果您有N/2內核能夠在一個週期內添加兩個數字，則可以執行log2(N)週期中的操作。僞代碼用於快速並行方法：

while N > 1: 
    N = N/2 
    for i in 0..N: // in parallel 
     X[i] += X[i + N] 
// result in X[0] 

，而不是一個簡單方法：

accum = 0 
for i in 0..N: // in serial 
    accum += X[i] 
// result in accum 

瓶頸防止並行在幼稚情況下是「減少」進accum。我認爲任何交換還原操作（加法，標量乘法等）都可以如上所述並行化。

另一個實際的考慮是CPU和GPU處理器內核可以在單個「週期」（例如SSE）中進行多次添加。

Big-O不突出減少瓶頸，並不一定反映在實時測量的時間複雜度。