时间复杂度: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;
    }
}

对于inner for-loop,它运行了很多次: 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)