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

循序渐进，根据代码片段，得到：

Time Complexity: O(logN) or O(N)?