かなーり前に、以下の記事を投稿した。
アルゴリズムにおける計算量の考え方だ。
計算量とは？プログラムの性能を計ってみよう | Shino’s Mind Archive
ここで、軽く対数について触れていた。
しかし、これを実際に計算量として使う場合、
どういう考え方になるのか、
という部分を解説していないことに気づいた。
というわけで、今回は改めて対数の基礎に触れ、
それが計算量としてどう出てくるのかを解説していこう。
苦手だ、という方にも分かるよう、
できるだけ詳しく解説していく。
対数とは
対数の定義
対数は、指数と関わりが深いお話だ。
例えば、ある数\(b\)を\(c\)乗すると\(a\)になる、
という関係があったとしよう。
これを、指数の考え方で表すと以下のようになる。
$$a = b^c$$
これは問題ないと思う。
このように、指数は、
累乗した結果、どういう数字になるか
という考え方だ。
だから、
累乗した結果である\(a\)を表すような形になっている。
では、対数の考え方で見てみよう。
対数は、
ある数を累乗して別の数字になったとき、何乗したのか
という考え方だ。
つまり、上の\(a, b, c\)で言うと、\(c=\)の形になるのだ。
これを表すために、新しい記号\(\log\)を導入して、
以下のように書き表す。
$$c = \log_b(a)$$
\(b\)を\(a\)にするためには、\(c\)乗すればよい。
これが、対数の定義だ。
また、言葉の定義になるが、
上式の\(b\)を底、\(a\)を真数と呼ぶ。
対数の基本的性質
基本的性質、と書いたが、計算のしかただ。
前にも紹介した以下4つについて、
なぜ成り立つのか軽く説明しておこう。
- 対数の加算
\(\log_c(a) + \log_c(b) = \log_c(ab)\) - 対数の減算
\(\displaystyle \log_c(a) – \log_c(b) = \log_c(\frac{a}{b})\) - 対数の定数倍
\(b\log_c(a) = \log_c(a^b)\) - 性質
\(\log_a(a) = 1\)
対数の加算
以下を示そう。
$$\log_c(a) + \log_c(b) = \log_c(ab)$$
まず、\(\log_c(a) = x, \log_c(b) = y\)と置く。
で、対数の定義から、\(a = c^x, b = c^y\)と表せる。
この両辺を掛けよう。
$$ab = c^x \times c^y = c^{x + y}$$
対数の定義から、
$$x + y = \log_c(ab)$$
\(x, y\)を元に戻して…
$$\log_c(a) + \log_c(b) = \log_c(ab)$$
より、成立する。
対数の減算
こちらは、上の加算のうち、
両辺を掛けた部分を割ることで示せる。
同じように示していこう。
$$\log_c(a) – \log_c(b) = \log_c(\frac{a}{b})$$
まず、\(\log_c(a) = x, \log_c(b) = y\)と置く。
で、対数の定義から、\(a = c^x, b = c^y\)と表せる。
ここまでは同じ。
では、今度は割り算をする。
$$\frac{a}{b} = \frac{c^x}{c^y} = c^{x – y}$$
もうなんとなく分かると思うが、
また対数の定義から変形しよう。
$$x – y = \log_c(\frac{a}{b})$$
そして、\(x, y\)を元に戻す。
$$\log_c(a) – \log_c(b) = \log_c(\frac{a}{b})$$
これで成立だ。
対数の定数倍
今度は定数倍だ。
$$b\log_c(a) = \log_c(a^b)$$
まず、\(\log_c(a) = x\)と置く。
対数の定義から、
$$a = c^x$$
両辺\(b\)乗して、
$$a^b = (c^x)^b = c^{bx}$$
また対数の定義を使って変形する。
\(c\)を\(a^b\)にするには\(bx\)乗すればいいので、
$$\log_c(a^b) = bx$$
あとは、\(x\)を元に戻せば…
$$\log_c(a^b) = b\log_c(a)$$
となり、成立する。
性質
…これを一言で言い表すうまい言い方が思いつかなかった。
$$\log_a(a) = 1$$
これは、定義を考えれば簡単だ。
\(a\)を\(a\)にするには何乗すればいいかなので、
そのまま…つまり1乗すればいい。
計算量で出てくる例
さて、ようやく計算量の話が出てくる。
上で説明したような数がどうやって計算量に出てくるか、
具体的なアルゴリズムを一つ紹介しよう。
ずばり、二分探索が当てはまる。
二分探索
二分探索は、
多量のデータから特定のデータを探すときに使われる
探索アルゴリズムの一つ。
アルゴリズムを以下に示そう。
入力は二つ、
データ群をdata配列、
探したいデータをvalueとする。
ただし、data配列の中身は
小さい順に並んでいる必要がある。
出力は、data配列の0から数えて何番目にデータが入っているか、
見つからなかった場合は-1を返す。
- 変数
lowに0、highにdata配列の長さ-1を代入しておく。 - 変数
midに、(low + high)/2を代入しておく(小数点以下切り捨て)。 low <= highである間、以下を繰り返す。- もし
data[mid]とvalueが等しいなら、見つかったのでmidを返す。 - もし
data[mid]よりvalueが小さいなら、highにmid-1を代入する。 - もし
data[mid]よりvalueが大きいなら、lowにmid+1を代入する。
- もし
- 見つからなかったとして、
-1を返す。
ちょっとこれだけだと分かりづらいので、図を用意した。
探す範囲を半分ずつ減らしているのが分かるだろうか。
このように、ある数に注目して、
探している数がそれより大きいか小さいかで
範囲を狭めていくのが、この二分探索だ。
で、このどちらに入っているかを分かるようにするために、
データが昇順で並んでいる必要があるのだ。
二分探索の計算回数
では、何回の計算をしているかを簡単に数えてみよう。
アルゴリズムの1, 2, 4は必ず1回、
計算量的には定数は無視するので省こう。
繰り返しでも比較だったり代入だったりをしているが、
ここも繰り返す1回につき行うものなので、定数倍となる。
これも計算量では無視できるので、最終的に
繰り返し回数がどうなるかだけ見ればいいことになる。
最悪なパターンで考えるのが普通だったので、
最後の一個でようやく見つかる、あるいは
見つからない場合で考えていこう。
ここからは、わかりやすさ重視で、細かい部分は気にしないでおく。
データ数がn個のとき、まず一回目で、
その前半、後半どちらにあるかが分かる。
つまり、次の探索はデータ数が半分になる。
もう一度繰り返すと、例えば一回目で前半だったら、
更にその前半、後半が分かるので、1/4に。
さらに次は1/8、次は1/16…というふうに、
探索するデータの数はどんどん1/2に減っていく。
これを繰り返して、
残り1個になるまでどんどん数を減らしていくのだ。
よって、この繰り返し回数は、
データ数nを、1になるまで何回2で割れるかという数になる。
この数を\(x\)としておこう。
この\(x\)とデータ数\(n\)について、
数式では以下のような関係式になっている。
$$\frac{n}{2^x} = 1$$
両辺に\(2^x\)を掛けよう。
$$n = 2^x$$
これを、\(x=\)の形に直せれば、計算量が書き表せる。
…さて、何か思い出さないだろうか。
そう、本記事前半で説明した対数が使えるのだ。
対数の定義に従って書き直すと…
$$x = log_2(n)$$
こうなる。
よって、二分探索の計算量は\(O(\log_2(n))\)となるのだ。
…が、実際に扱われる表記では、
底の2を省略して、\(O(\log(n))\)と書き表す。
計算量における対数の底
ほとんどの場合、計算量における対数の底は2とされている。
なぜ2なのかはちょっと分からないのだが、
実は底がいくつであろうと、計算量には影響しない。
これも証明…するのだが、その前に対数の性質をもう一つ紹介しよう。
$$\log_a(b) = \frac{\log_c(b)}{\log_c(a)}$$
そう、底を変換できるのだ。
では、まずこれを証明する。
\(\log_a(b) = x\)と置くと、
対数の定義から、\(b = a^x\)と分かる。
両辺を底\(c\)の対数を取って、
$$log_c(b) = \log_c(a^x)$$
対数の定数倍の性質から、
$$log_c(b) = x\log_c(a)$$
両辺を\(\log_c(a)\)で割って、ついでに両辺入れ替えて、
$$x = \frac{\log_c(b)}{\log_c(a)}$$
最後に、\(x\)を元に戻して、
$$\log_a(b) = \frac{\log_c(b)}{\log_c(a)}$$
これで、数式は証明完了だ。
で、例えば底が10のような計算量\(O(\log_{10}(n))\)で考えよう。
底の変換を行うと、
$$\log_{10}(n) = \frac{\log_2(n)}{\log_2(10)}$$
と直せる。
この、\(\log_2(10)\)は定数だ。
つまり、計算量の観点からは無視できる。
よって、計算量においては、
底がいくつというのは影響しないのだ。
だから、基本的に2として、省略している、というわけだ。
まとめ：計算量における対数
今回は、計算量でたまに出てくる対数を深堀りしてみた。
具体例としては二分探索しか出していないが、
他にもソートアルゴリズムの
クイック、マージ、ヒープソートの計算量もこの対数が出てくる。
なかなかとっつきにくい内容であるのは確かなのだが、
ある数で何回割れるか、という考え方がいいかもしれない。
コメント