为什么这个算法的时间复杂度是O(N)？

Question

4

以下的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;  
    }
}

有人可以解释一下这个问题吗？

提前感谢！

- user2109258

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

20

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

- Paul Hankin

非常感谢！应该在系列课程中多加注意哈哈。 - user2109258

2

@user2109258 这实际上是一个著名的系列问题，想象一下一个人和他的狗，它们一起去同一个地方，狗的速度是人的两倍，所以当狗到达目标时，它会回到人身边，当狗回到人身边时，它又返回他们的目标，如此往复，直到人到达目标。问题是狗总共走了多少距离？ - Iharob Al Asimi