time-complexity - 时间复杂度 : O(logN) or 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 是公共(public)比率)。

它的总和可以用下面的公式计算:

在这种情况下，和的限制是2，所以:

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

因此同谋度是 O(N)