アルゴリズムの計算量について
「O(log n)とO(n log n)が小さいことだけ覚えておけばいいんだよ」と教えられたことはないでしょうか？私は誰に教わったかは覚えていませんがあります。
ですが実際問題O(log n)の計算量はなぜ少なくなるのでしょうか。
調べるうちにイメージがつかめたため、自分用のメモと今後の宿題を残したいと思います。
この記事でわかること
- なぜO(log n)の計算量が小さいのか
O(1)、O(n)、O(log n)の順番でイメージをつかむ
O(1)の計算量
例えば配列の中の要素にアクセスする際array[10]と入力して、データのアクセスする場合などがO(1)の例になります。
（この例だと、事前に配列のどこに必要な要素があるか把握している必要があります）
O(n)の計算量
線形探索のように、前から後ろ（逆も可）に探索していくと、最悪の計算量はデータ数であるnに一致します。つまり最悪、データ数の数だけ探索するようなアルゴリズムです。
O(log n)の計算量
logという言葉を聞くと非常に難しい雰囲気が出てきます。
ですので、まずは二分探索の計算量をlogなしで計算してみることにします。
（ちなみに二分探索の計算量はO(log n)です）
n=64の時、二分探索をツリー上に表すと以下のようになります。
コンパクトに収める都合上、ツリーは省略して書いています。
64
/ \
/ \
32 32
/ \
16 16
/\
8 8
/\
4 4
/\
2 2
/\
1 1←右のコッチが答えだとします
64から求めたい1つの答えまでたどり着くのに、6回数字を半分に分けました。なのでこの時の最悪の計算量は「6」ということになります。logを使わずとも、計算量を求めることができました。そして確かにO(n)より小さいです。
しかし毎回ツリーを描くのは難しいです。64でも相当骨が折れます。何とか簡単に計算できないでしょうか？
そこでlogが登場します。
例えばlog2 64 = Xの場合、2を何乗したら64になりますか？ということを問われています。2は6乗すると64になるので、X=6です。
logとはある数を何乗したらこの数になりますか？ということを表す式なのです。
log2 64 = 6 のような式においてlogの右隣にある2のような数を「底」と呼びます。アルゴリズムの計算においてはほとんどの場合（どれくらいほとんどかは不明ですが）「底」を2と暗黙的に決めています。
なのでO(log 64)ならO(log2 64)と読み替えてもほぼ問題はない（そうです）。
ですからO(log 97384798)だろうがO(log 638749873)だろうが計算することができます。
これは「底」が違うことによる計算量の違いが、たかだが定数倍にしかならないからだとされています。つまり小さいということ（らしい）です。
この辺の理解は「異なる底の定数倍の違い」を理解する、という宿題として次回の記事で書けるようになりたいと思います。
最後にO(n)とO(log n）の計算量の違いをグラフにしてみました。
赤：O(n)
青：O(log n）
グラフからもわかるようにO(n)と比較すると、O(log n)はデータ数が増えても、計算量の増加具合が緩やかです。
つまり、私に教えてくれた方はこのイメージさえつけておけば大丈夫というのを伝えたかったんですね。なるほどー。
まとめ
O(log n)の計算量はやっぱり小さい。