algorithm - whileループの実行時間（数学）

Question

そのため、次のループの数式が必要ですが、理解できないようです。単純なものが欠けているだけだと思います。

while a <= b
    a = a + a
end

分析を使用すると、この関数の実行時間はどのくらいになりますか？

Answer 1

実行時間は、の対数に依存しbます。言い換えれば、時間計算量はO(log N)です。

aこれは、1と256から開始するとわかりますb。ループを通過するたびに、a反復が9回になるように2倍になります（条件がだった場合は8回になります< b）。

値を2倍にするたびbに、1回の追加の反復が発生します。

もちろん、これは複雑さの分析であり、実行時間は次のような他の多くの要因に依存します（ほぼ確実に網羅的なリストではありません）。

• あなたのマシンはどれくらい速いか。
• それが同時にしなければならない他のこと。
• a：の初期値a == 0は無限の実行時間をa == b + 1与え、一定の実行時間を与えます。

Answer 2

ループの各反復が2倍になることに同意しますaか？その場合a、初期値を1にします。1回の反復の後、a == 2。2回の反復後a == 4。3の後、a == 8。4の後、a == 16; 等々。

それを仮定しb == 64ます。この場合、ループは7回の反復を実行します。それを観察してlog_2(64) == 6ください。

それを仮定しb == 128ます。この場合、ループは8回の反復を実行します。それを観察してlog_2(128) == 7ください。

それを仮定しb == 256ます。この場合、ループは9回の反復を実行します。それを観察してlog_2(256) == 8ください。

したがって、実行時間はの対数に依存しbます。

Answer 3

a毎回倍増しているのでlog(b/a)、ループが終了する前に倍増する必要があります。したがって、実行時間はTheta(log(b/a))です。