はじめに

計算量オーダーについてlogだけにフォーカスした記事が無かったので執筆に至ります。

TL;DR

アルゴリズムの計算では、検索範囲 = 2^(探索回数)という場面がある。
その対数を取れば log2 (検索範囲) = 探索回数 となるから。

なぜなのか

アルゴリズムの計算量においてO(logn)のもっとも有名な例の一つである、二分探索の例を取ってみよう。
ざっくり二分探索について説明しよう。ニ分探索というのは、私達の生活にも無意識に使われている。

例えば私達が分厚い辞書から「121ページ目を開け」と言われた場合、
私達は、1000ページある辞書なら500ページ目から開き、次はその前半の半分250ページ目を開けるだろう。この繰り返しで121ページ目にたどり着く。
このような対象を二つに分ける探索、つまりこれがニ分探索である。

詳しくは アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より参照

実は、この二分探索の見方を変えると、x回探索をした場合2^xの範囲探索できるのです。

表1 二分探索の探索回数と検索範囲の関係

つまり、探索回数と検索範囲の関係は検索範囲 = 2^(探索回数)と記述できます。
その対数を取ればlog2(検索範囲) = 探索回数 となるためlogが出現してくるのです。

ここで、探索回数というのは計算量オーダーであり、検索範囲というのはデータ数nであるため、
計算量オーダー = log2(n)となるわけです。

ここでlog2というのは底の変換公式で、(定数)log(n)という形に変換できる。
計算量オーダーにおいて定数は無視できるので一般的にはO(log(n))となるわけです。

以上のように、計算量オーダーのlogにおいて分からなくなる点が私的には二つあり、
なぜlogが出てくるのかというのと、なぜ底が2で無いのかというのがクリアになれば幸いです。