我知道下面的代码具有O(log(n))的复杂性:

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

我知道在这里,n在每次迭代中被分成两半,这意味着如果n是1000,那么需要10轮才能脱离循环这是如何导致o(log(n))的?
很抱歉这个简单的问题,我真的尽力在我问之前得到它。

最佳答案

每次通过循环,您都要除以2(大致上;这将忽略舍入,因为它是一个渐近参数)所以如果n=n在开始,经过k次迭代,n=n/(2^k)。要得到n=1,必须满足2^k=n,即k=log(n)。

关于c - 为什么counter = counter/2;有O(log(n))吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/5381081/

10-08 22:47
查看更多