为什么 counter = counter /2;有 O(log(n))？
我知道以下代码的复杂度为 O(log(n))：
while (n>1)
{
counter++;
n/=2;
}
我知道这里，n 在每次迭代中被分成两半，这意味着如果 n是 1000 则需要十轮才能跳出循环。这是如何导致 O(log(n)) 的？
抱歉问了这个简单的问题，在问之前我真的尽力了。
I know the following code has a complexity of O(log(n)):
while (n>1)
{
counter++;
n/=2;
}
I understand that here, n is being divided in half on each iteration, meaning that if n was 1000 then it will take ten rounds to get out of the loop. How did this lead to O(log(n))?
Sorry for the simple question, I really tried my best to get it before I asked.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
每次循环时，您都会除以 2（粗略地；这将忽略舍入，因为它是渐近参数）。因此，如果开始时 n = N，则经过 k 次迭代后，n=N/(2^k)。要达到 n = 1，您必须满足 2^k = N。即 k = log(N)。
Each time through the loop, you divide by 2 (roughly; this will ignore rounding since it is an asymptotic argument). So if n = N at the start, after k iterations, n=N/(2^k). To arrive at n = 1, you have to satisfy 2^k = N. That is, k = log(N).
递推关系将是
尝试使用 Master 定理 来解决它，将给出 T(n ) 为 O(log n)（类似于二分查找中得到的结果）。
The recurrence relation would be
Trying to solve it using Master's theorem will give the running time of T(n) as O(log n) (similar to what you get in Binary Search).
假设 n 是 2^x（例如 2^5=32、2^10=1024 等），因此计数器在循环内递增 x 次。根据定义，x 是以 2 为底的 log n。
Imagine that n is 2^x (e.g. 2^5=32, 2^10=1024 etc), so that the counter is incremented x times within the loop. By definition, x is a base 2 log n.
根据定义，对数不是线性的。换句话说，它们根据输入的不同而改变不同的量。在您的示例中，第一步将
n减少了 500，而第五步仅将其减少了 32。越接近 1，n减少的速度就越慢。这种“减速”正是日志所表现出的行为。By definition, logarithms aren't linear. In other words, they change by different amounts depending on the input. In your example, the first step takes
ndown by 500, while the fifth step reduces it by only 32. The closer you get to one, the slowerndecreases. This "deceleration" is exactly the kind of behavior you get with a log.一个简单的解释：如果你加倍 n 会发生什么？运行时间是否加倍（即 O(n)）？不，运行时间仅增加一步。这是典型的 O(log n)。
[OTOH，如果你对 n 进行平方（假设它从 4 增加到 16），那么你会发现步数加倍。再次表示 O(log n)。]
A simple hand-wavey explanation: What happens if you double n? Does the runtime double (that would be O(n))? No, the runtime increases by only one step. This is typical of O(log n).
[OTOH, if you squared n (say it increased from 4 to 16), then you find the number of steps double. Again, indicative of O(log n).]