algorithm - この関数/ループがO（n）ではなくO（log n）であるのはなぜですか？

Question

この関数はO（log（n））です。なんで？nまでループしていませんか？

function fxn($n) {
    for ($i = 1; $i <= $n; $i *= 2)
        echo $i;
}

ちなみに私はO（n）分析にかなり慣れていません。この関数はnまでループするので、確かにO（n）に見えます。

Answer 1

すべての要素をループしているわけではありません。各ステップで、前のステップの要素の2倍をジャンプし$i *= 2ます。つまり、$iがゼロより大きい値で始まると仮定すると、それ以外の場合は無限ループになります。$i常に0書き込まれたとおりになります。

Answer 2

コードは、O(n) になる 1 (または任意の定数値)までループしますが、ループしnません。

これはそれが何をするかです：

       1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
       |  |     |           |                       |
       +--+-----+-----------+-----------------------+
Steps    1    2        3               4

毎回 2 倍になるため、実際には O(log N) になります。これは、二分木検索が反復ごとに検索空間を半分にするのと同様です。

Answer 3

注： 0から開始し、0 * 2 = 0であるため、関数が終了することはありません。ループは1から開始すると仮定します。

ループは毎回2の倍数でO(lg(n))増加します。これが、ランタイムがである理由です。

n=128の簡単な例を考えてみましょう。

各反復のiの値は次のとおりです：1、2、4、8、16、32、64、128。したがって、8つの値を通過しました。

lg(128) = 7 (lg = log in base 2)
        = 8 - 1

ここで、- 1は定数であるため、実行時の計算には影響しないことに注意してください。

ループが1（または任意の定数k）だけインクリメントされる場合、実行時間はO（n）になります。ここで考慮すべき重要なことは、等比数列と算術級数の違いです。これにより、さまざまなランタイムが得られます。

Answer 4

このループは O(n) になります。

function fxn($n) {
    for ($i = 0; $i <= $n; $i++)
        echo $i;
}

$i値を取るため：

1, 2, 3, 4, 5, 6, 7, ..., n

しかし、このループは O(log(n)) だけです:

function fxn($n) {
    for ($i = 1; $i <= $n; $i *= 2)
        echo $i;
}

$i値を取るため：

1, 2, 4, 8, 16, 32, 64, ..., n

そして、そのように大きくなる数列を「対数」と呼びます。