はじめに
計算量オーダーについてlogだけにフォーカスした記事が無かったので執筆に至ります。
TL;DR
アルゴリズムの計算では、検索範囲 = 2^(探索回数)という場面がある。
その対数を取れば log2 (検索範囲) = 探索回数 となるから。
なぜなのか
アルゴリズムの計算量においてO(logn)のもっとも有名な例の一つである、二分探索の例を取ってみよう。
ざっくり二分探索について説明しよう。ニ分探索というのは、私達の生活にも無意識に使われている。
例えば私達が分厚い辞書から「121ページ目を開け」と言われた場合、
私達は、1000ページある辞書なら500ページ目から開き、次はその前半の半分250ページ目を開けるだろう。この繰り返しで121ページ目にたどり着く。
このような対象を二つに分ける探索、つまりこれがニ分探索である。
詳しくは アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より参照
実は、この二分探索の見方を変えると、x回探索をした場合2^xの範囲探索できるのです。
| 探索回数 | 検索範囲 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 6 | 64 |
表1 二分探索の探索回数と検索範囲の関係
つまり、探索回数と検索範囲の関係は検索範囲 = 2^(探索回数)と記述できます。
その対数を取ればlog2(検索範囲) = 探索回数 となるためlogが出現してくるのです。
ここで、探索回数というのは計算量オーダーであり、検索範囲というのはデータ数nであるため、
計算量オーダー = log2(n)となるわけです。
ここでlog2というのは底の変換公式で、(定数)log(n)という形に変換できる。
計算量オーダーにおいて定数は無視できるので一般的にはO(log(n))となるわけです。
以上のように、計算量オーダーのlogにおいて分からなくなる点が私的には二つあり、
なぜlogが出てくるのかというのと、なぜ底が2で無いのかというのがクリアになれば幸いです。