【Big O】対数・再帰の実行時間、基数省略について【二分探索】

こんにちは。タクマ™ [@suwaru_blog] です。

実行時間 O(log N) について

実行時間 O(log N) について解説していきます。

対数における基数: 省略する

そもそも log N と基数が省略されていますが、
Big O 記法で対数の基数は問題にならないのでそうなっているのです。

対数の基数は省略しても定数倍の差しかないのでノーカンということです。
※ これは前回の記事で説明した「定数切り捨てルール」に起因します。

二分探索 (バイナリサーチ)

実行時間 log N となる代表的なアルゴリズムは「二分探索」です。

昇順で値が並んだ要素をもった配列があるとします。
その中から特定の値の場所を見つけたい場合、二分探索が有効です。

たとえば {1, 5, 8, 9, 11, 13, 15. 19, 21}から 9 の位置を探りたいとしましょう。

実行時間

要素数がどのように遷移していくかに注目しましょう。

合計の実行時間は「要素数が N から 1 になるまで何ステップか？」で表現できます。

要素数が 16 の場合

たとえば、要素数 16 の配列を二分探索するとしましょう。
その場合は以下のように要素数が遷移します。

対象となる要素数は 1/2 になっていき、
① 16 → 8 ② 8 → 4 ③ 4 → 2 ④ 2 → 1 …の合計 4 ステップが存在します。

話をわかりやすくするため、これを逆順にしてみましょう。

対象となる要素数は 2 倍になっていき、さっきと同じく 4 ステップが存在します。

これは 2^4 = 16 の実行時間だと表現することができます。
対数をつかうと log[2]16 = 4 という実行時間で表現することもできます。

要素数が N の場合

2^k = N を対数で表現すると log[2]N = k と表現することができますね。
基数を省略すると log N になります。

平衡二分探索木の実行時間も O(log N)

平衡二分探索木というアルゴリズムもあるのですが、
こちらも同じ理由で O(log N) となります。

再帰の実行時間について

再帰の実行時間について解説していきます。

再帰の実行時間は O(N^2) にならない

以下のコードは関数 f を再帰実行しています。

int f(int n) {
    if ( <= 1) {
        return 1;
    }
    // 関数 f を再帰実行
    return f(n - 1) + f(n - 1);
}

再帰の実行時間は O(枝の本数^レベル)

たとえば f(4) を実行すると、関数は合計 15 回実行されます。
計算式は 2^0 + 2^1 + 2^2 + 2^3 で 15 回です。

f(4)             - レベル0
├── f(3)         - レベル1
│   ├── f(2)     - レベル2
│   │   ├── f(1) - レベル3
│   │   └── f(1) - レベル3
│   └── f(2)     - レベル2
│       ├── f(1) - レベル3
│       └── f(1) - レベル3
└── f(3)         - レベル1
    ├── f(2)     - レベル2
    │   ├── f(1) - レベル3
    │   └── f(1) - レベル3
    └── f(2)     - レベル2
        ├── f(1) - レベル3
        └── f(1) - レベル3

レベルが 1 つ深くなると、枝が 2 本はえて、ノードの数は 2 倍になっています。

実はレベル 0 からレベル N までの合計ノード数は 2^N+1 - 1 となっており、
再帰関数を使ったときの実行時間は O(枝の本数^深さ) と表現できます。

今回は枝が 2 本生えるパターンなので、レベル N のとき O(2^N) となります。

指数における基数: 省略できない

たとえば 8^N と 2^N を比較してみましょう。
8^N の基数は 8 ですが、これを基数 2 に変換してみます。

さすがに 2^2N と 2^N では結果が違いすぎるのは想像できると思います。
指数における基数は省略してはいけない、ということを覚えておいてください。

CS シリーズ

次回

前回