为什么counter = counter /2；有O(log(n))？

Question

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

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

我知道在这里，n在每次迭代中被一分为二，这意味着如果n是1000，那么它将需要10轮才能走出循环。这是如何导致O(log(n))的？

对于这个简单的问题，我真的很抱歉，我真的尽力在我问之前得到它。

Answer 1

每次循环时，都要除以2(粗略地说，这将忽略四舍五入，因为它是渐近参数)。因此，如果n=N，在k次迭代之后，n=N/(2^k)。要得到N = 1，你必须满足2^k =N，即k= log(N)。

Answer 2

递归关系为

 T(n) = T(n/2) + O(1)

尝试使用Master's theorem来解决它，会得到T(n)的运行时间为O(log )(类似于您在二进制搜索中得到的结果)。

Answer 3

假设n是2^x (例如2^5=32、2^10=1024等)，因此计数器在循环中递增x倍。根据定义，x是以2为底的log。