为什么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).