#はじめに
計算量オーダーについて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で無いのかというのがクリアになれば幸いです。