为什么这个算法是 O(N)？

Question

下面的 C 代码显然是 O(N)（根据我的练习考试）。但是，我不确定为什么它是 O(N) 而不是 O(Something*Something)。

void doit(int N) {
    while (N) {
        for (int j = 0; j < N; j += 1) {
        }
        N = N / 2;  
    }
}

有人愿意给我一些关于这个问题的见解吗？

提前致谢！

Answer 1

因为 N + N/2 + N/4 + ... = 2N.