已关闭。此问题需要更多的focused。当前不接受答案。
**想要改进此问题吗？**更新问题，使其仅关注editing this post的一个问题。
昨天关门了。
Improve this question
下面是一个简单的Java代码：
while(i>1)
{
i = i/2;
}我很难理解如何进行数学计算来知道它的时间复杂度是O(logn)。我如何用简单的方法来证明呢？
已关闭。此问题需要更多的focused。当前不接受答案。
**想要改进此问题吗？**更新问题，使其仅关注editing this post的一个问题。
昨天关门了。
Improve this question
下面是一个简单的Java代码：
while(i>1)
{
i = i/2;
}我很难理解如何进行数学计算来知道它的时间复杂度是O(logn)。我如何用简单的方法来证明呢？
3条答案
按热度按时间r3i60tvu1#
你需要多少次将i除以2，直到它变成1？
i / 2n = 1
i = 2n
已知log 2（a）= B意味着2b = a，我们得到
n = log2（i）
因此，循环的复杂度是O（log 2（i））=O（log（i））。
ohtdti5x2#
i=10个
6/2=5 -〉5/2=2 -〉2/2=1
O（logn）是一个复杂度为O（log 2n）整数运算。
9jyewag03#
假设i是
int，i的二进制表示在每次循环迭代中从右边丢失一位，直到它为0，这意味着迭代的总次数是表示i所需的位数。表示i所需的位数是ceil（lg（i））+1，可以使用基本对数规则的变化和big-Theta的定义将其表示为Theta（log n）。