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

指数

$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分探索など

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

おわり。

なっとく! アルゴリズム