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

  • このエントリーをはてなブックマークに追加
  • Pocket

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

今回は「実行時間 O(log N) 」と「再帰の実行時間」について解説します!

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

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

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

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

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

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

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

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

二分探索では、要素の中央値とさがしたい値の大小比較を行いながら場所特定します。

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

  • {1, 5, 8, 9, 11, 13, 15. 19, 21}
    • 中央値は 11
      • 9 < 11 なので 11 より左側に 9 は存在する
  • {1, 5, 8, 9, 11}
    • 中央値は 8
      • 8 < 9 なので 8 より右側に 9 は存在する
  • {9, 11}
    • 9 と 9 を比較すると一致
      • 9 の 位置 (index) を return する

実行時間

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

探索対象は要素数 N の状態から開始されます。
次のステップに入ると、探索対象となる要素数は N/2 になり、
次のステップに入ると、探索対象となる要素数は N/4 になり、
特定できると要素数は 1 になります。

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

要素数が 16 の場合

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

  • N = 16
  • N = 8
  • N = 4
  • N = 2
  • N = 1

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

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

  • N = 1
  • N = 2
  • N = 4
  • N = 8
  • N = 16

対象となる要素数は 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(log N) となります。

再帰の実行時間について

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

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

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

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

この場合、2 箇所で関数を呼んでいるので実行時間は O(N^2) になるでしょうか?
いいえ、O(2^N) になります。

再帰の実行時間は 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 – f(4)
    • ノード数: 2^0 で 1
    • 合計ノード数: 1
  • 深さレベル1 – f(3)
    • ノード数: 2^1 で 2
    • 合計ノード数: 1 + 2 = 3
  • 深さレベル2 – f(2)
    • ノード数: 2^2 で 4
    • 合計ノード数: 3 + 4 = 7
  • 深さレベル3 – f(1)
    • ノード数: 2^3 で 8
    • 合計ノード数: 7 + 8 = 15
  • 深さレベルN – f(n)
    • ノード数: 2^N
    • 合計ノード数: 2^N+1 - 1

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

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

ちなみに空間計算量は O(N) となります。合計 O(2^N) のノードが生えますが、一度に生じるノードは最大 O(N) なのでメモリは O(N) だけあればよいことなります。

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

log の基数は大した問題じゃないので省略されるといいましたが、
指数における基数は大きな問題なので省略できません。

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

  • 8^N
    • = (2^3)^N
    • = 2^3N
    • = 2^2N * 2^N
  • 2^N

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

CS シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

コメント

コメントを残す

*