时间复杂度：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

按照代码片段逐步进行，我们获得：