指数・対数とビッグオーと線形時間と対数時間について。

指数


$2^3 = 8$

これの3のことを指数という。

対数


いわゆるこれ→ $\log_{2} x$

「xを何乗すればyになるか」というのを対数という。例えば

$\log_{2} 8 = x$

この場合「底を2とする8の対数」という。

指数と対数


要するに指数をひっくり返すと対数になる。

指数対数
$2^3 = 8$$\log_{2} 8 = 3$
$2^4 = 16$$\log_{2} 16 = 4$

ビッグオー


計算量を評価するのに用いられる記法をオーダ記法という。その中でも $O(n)$ みたいな $O$ を使うやつのことをビッグオーという。 $(n)$ の部分が計算量を表す。

線形時間と対数時間


$O(n)$線形時間データ量の分だけ時間がかかる配列走査など
$O(logn)$対数時間処理毎に処理対象を減らすことができる2分探索など

計算量のイメージの図は雑に書くと下記のようになる。

おわり。

参考書籍


なっとく! アルゴリズム