需要帮助来理解此代码的 Big-O 复杂性的答案

Question

根据答案键，答案为O(N)。我没有足够的时间仔细看它。我认为在第一个循环中是 i++ 而不是 i/=2 所以我写了 O(N^2)。但是现在我不确定什么是正确的。我觉得应该是O(log n * log n).

代码：

int count = 0;
for (int i = N; i > 0; i /=2)
    for (int j = 0; j < i; j++)
        count++;

图片：

Answer 1

• 外循环第一次迭代，内循环执行N次
• 在第二次迭代时，内循环执行N/2次
• 在每次后续迭代中，内循环的执行次数是前一次迭代的一半

总迭代次数等于N + N/2 + N/4 + ... + 1，约等于2N。

因此总迭代次数为O(N)