根据答案，答案是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++;
图片:
最佳答案
- 在外循环第一次迭代时，内循环执行N次
- 在第二次迭代时，内循环执行 N/2 次
- 在每次后续迭代中，内循环的执行次数是前一次迭代的一半
迭代总数等于 N + N/2 + N/4 + ... + 1，约等于 2N。
因此，总迭代次数为O(N)
关于c - 需要帮助来理解此代码的 Big-O 复杂性的答案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68282087/