指数・対数とビッグオーと線形時間と対数時間について。
指数
$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分探索など |
計算量のイメージの図は雑に書くと下記のようになる。
おわり。
