時間複雜度：O（logN）或O（N）？

Question

我認爲下面代碼的時間複雜度是O（log N），但答案是O(N)。我不知道爲什麼：

int count = 0; 
for (int i = N; i > 0; i /= 2) { 
    for (int j = 0; j < i; j++) { 
     count += 1; 
    } 
} 

對於內部件for循環，它運行很多次： N + N/2 + N/4 ...

這似乎是logN我。請幫我理解爲什麼在這裏。謝謝

Answer 1

1，1/2，1/4，1/8 ... 1/2 ** n是一個幾何序列，a = 1，r = 1/2（a是第一項，r是常見的比例）。

及其總和可以使用以下公式來計算：

在這種情況下，總和的限度是2，所以：

n + n/2 + n/4 ... = n(1 + 1/2 + 1/4...) -> n * 2 

因此串通是O（ N）

Answer 2

按照代碼片段逐步進行，我們獲得：