为什么这个算法是O(N)？ [英] Why is this algorithm O(N)?

问题描述

下面的C代码显然是O(N)(根据我的模拟考试)。但是，我不确定为什么是O(N)而不是O(某物*某物)。

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

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

提前感谢！

推荐答案

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

这篇关于为什么这个算法是O(N)？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！