アルゴリズムが持つ計算量にlogが出てくるのをきちんと理解する

f:id:sattamassagana:20150615211730j:plain

計算量が1とか2なら分かる

アルゴリズムが持つ処理の複雑さの尺度を計算量という。殆どの場合、アルゴリズムの処理時間の尺度のことをいう。とはいえハードウェアやソフトウェアの性能によるところが大きすぎるので、せいぜい「このアルゴリズムの実行時間は、要素数の3乗に比例する」というような言い方になる。そしてこれが例えば1とか2ならまあ分かる。要素がn個あったらn回だか、n時間掛かる、計算量がnということ。

log2n?

そんな中、計算量にlogが出てくる。イメージしづらい。数値の大小関係を考える。

  log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!

例えば2分探索木は平均比較回数がlog2nと言われる。いったい何回なんだ。という疑問からはじまる。

 さて、このnをまず分かりやすくするために仮に2000とする。要素数が2000の場合の計算量を求めるということになる。平均比較回数がlog22000、まだわからない。

これをこのように考える。

  1024 < 2000 < 2048

1024は210で、2048は211だから、

  210 < 2000 < 211

そして2を底とする対数をとると

  10 < log22000 < 11

というわけで、平均比較回数自体は10回となる。