while循环执行多少次？

Question

昨天我申请了计算机工程硕士学位,这是他们的问题之一.我无法解决它,所以我非常好奇.

...
i = 1;
while (i <= n)
{
    i = i * 2;
}
...

这个while循环执行多少次,请将您的答案作为公式.例如:log n ...

谢谢

Answer 1

在循环的第x ^次迭代中,i等于2 ^x(您可以通过归纳轻松证明这一点).假设X迭代之后的循环停止,这是指N <2 ^X.这也意味着在迭代X-1上,循环仍在运行,因此2 ^X- 1≤n.换一种说法 :

2 ^X- 1≤n<2 ^X.

从那里,找到X作为log ₂(n)的函数很容易.