algorithm - whileループは何回実行されますか？

Question

昨日、私はコンピュータ工学の修士号を申請しましたが、それは彼らの質問の1つでした。私はそれを解決することができなかったので、私は非常に興味がありました。

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

このwhileループが何回実行されるか、式として答えてください。例：log n .. ..

ありがとう

Answer 1

ループのx^{回目の反復では、2 x}iに等しくなります（これは誘導によって簡単に証明できます）。X回の反復後にループが停止するとします。これはn< ^2Xを意味します。これは、反復X-1でループがまだ実行されていたため、2X-1≤nであることも意味し^ます。言い換えると ：

2X ^- 1≤n< ^2X

そこから、log ₂（n）の関数としてXを見つけるのは簡単です。