c - 为什么 counter = counter/2;有 O(log(n))？

Question

我知道以下代码的复杂度为 O(log(n)):

while (n>1)
{
    counter++;
    n/=2;
}

我知道在这里，n 在每次迭代中被分成两半，这意味着如果 n 是 1000 那么需要十轮才能跳出循环.这是如何导致 O(log(n)) 的？

很抱歉这个简单的问题，在我问之前我真的尽力弄明白了。

Answer 1

每次通过循环，您除以 2(粗略地；这将忽略舍入，因为它是一个渐近参数)。因此，如果一开始 n = N，经过 k 次迭代后，n=N/(2^k)。要达到n = 1，你必须满足2^k = N。即k = log(N)。