为什么时间复杂度为O（log n）？
这个问题在这里已经有了答案：
如果你把n写成一个二进制数，比如说11011011 ，那么在循环结束之前所需的连续值就是
11011011
1101101
110110
11011
1101
110
11
1
因此，迭代次数（ k最终值）等于n的初始位数。 从
2^(k-1) ≤ n < 2^k
这是您绘制k位的条件
k-1 ≤ log2(n) < k.
原因在于循环，除法和加法中的操作是O（1）。 现在，考虑n = 2 ^ m的迭代次数，对于某些m，并将此数与log_2（n）进行比较。 推广到n，这不是2的幂是容易的。 用n（n）表示输入n的循环迭代次数，取2 ^ m <n <2 ^（m + 1），注意i（n）= i（2 ^ m）整数除法）。
你重复n除以2直到你达到1或更少。 因此，你的停止条件由（公式）表示（大致）用下面的公式表示：/ = 2 ^ k <=> log_2 n = k（/是代码中的整数除法）。 粗糙度是允许的，因为我们正在处理O（）并且常量将消失。
链接地址: http://www.djcxy.com/p/40023.html上一篇: Why is the time complexity O(log n)?
下一篇: What is the difference or separates O(log(n)) and O(n)?