アルゴリズムの計算量lognはどうやって導出されたの？

この記事は、Showcase Gig Advent Calendar 2022 19日目の記事です。

こんにちは、Showcase Gigでアプリケーションエンジニアをしている押野です。

私はアルゴリズムが好きで自分で実装することはもちろん、様々なサイトで情報を集めたりしているのですが 計算量 $${\mathcal{O}(\log n)}$$ の解説が、数学が苦手な人には少々薄いなと日々思っています。

そこで、この記事では読んだ人が $${\log n}$$ はそうやって出てくるのか！となるところを目指していきます。

logって何？おさらい

計算量に出てくるlogというのは、高校数学ⅡBで学習する対数のことです。
指数関数 / 対数関数のように、指数と一緒に習ったあれです。
対数について詳しく書くと記事の意図からそれてしまうので、
ここでは指数と対数に以下の関係性があることを抑えておきましょう。
この関係だけ知っておけばひとまずほかの知識は不要です。

$$
b=a^p
$$

$$
p=\log_ab
$$

二分探索の計算量から探ろう

アルゴリズムを学習している際、対数に初めて出会うのは何かというと、大抵は二分探索を学んでいるときではないでしょうか。
二分探索からどのように対数が出現するかを見ていきましょう。

二分探索とは

二分探索とは、ざっくり言うと以下のような探索の手法です。

ソート済みのリストに含まれる一意のデータから、特定の値を検索する際に、
リストの中央の値と検索する値の大小を比較し、どちらかに探している値が存在しないことを繰り返して
探索する手法。

使用できる条件はあるものの、リストの値を1つずつ検証するよりも圧倒的に速い速度で探索できます。
また、リストの値が非常に大きな値になっても高速に探索できます。

多くの情報源で二分探索を探すと、たいてい上のような概要の後に
「計算量は $${\mathcal{O}(\log n)}$$ になります。」
で解説が終わるのですが、この記事では何でその計算量が出てくるのかに迫っていきます。

※そのため、二分探索自体の詳しいことは記載しません。

具体例1. 8個のデータからあたりを探す

いくつか二分探索で行われる具体的な操作を見てみましょう。
8個のデータが入ったリストからあたりを探すとき、最大で以下の計算が行われます。

• 1回目の探索：リストの真ん中と探す値を比較する。残りのデータ数が4になる

• 2回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が2になる

• 3回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が1になる。探していた値があるか分かる

となり、8個のデータを3回探索することでデータの存在を確認できました。
このときの計算を式にしてみると以下のようになります。

$$
8\div2\div2\div2=1
$$

具体例2. 64個のデータからあたりを探す

同じようにもう1つ具体的な操作を見てみます。
今度はリストの数が増えて64個のデータが入ったリストからあたりを探すとき、最大で以下の計算が行われます。

• 1回目の探索：リストの真ん中と探す値を比較する。残りのデータ数が32になる

• 2回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が16になる

• 3回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が8になる

• 4回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が4になる

• 5回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が2になる

• 6回目の探索：残りのリストの真ん中と探す値を比較する。残りのデータ数が1になる。探していた値があるか分かる

となり、64個のデータを6回探索することでデータの存在を確認できました。
このときの計算を式にしてみると以下のようになります。

$$
64\div2\div2\div2\div2\div2\div2=1
$$

具体例を一般化してみる

ここで元のデータ数をN、探索した回数をnとし、具体例で出てきた計算に置き換えると以下のようになります。

$$
N\div2^n=1
$$

これを少し式変形してみましょう。 $${2^n}$$ をかけてみます。

$$
N=2^n
$$

どうやら、冒頭でおさらいした指数と対数の関係における、指数の形と同じになりましたね。
指数の形をそのまま対数の形に置き換えてみます。

$$
n=\log_2N
$$

ここでnは探索した回数ですので、これが計算量にあたります。
対数を導き出す事ができました！！

計算量において底は無視できる

先程導き出した $${\log_2N}$$ は、まだ一般的に解説される $${\log N}$$ の形になっていませんでした。

ここで $${\log_2N}$$ と $${\log_8N}$$ はどれくらい違うのかを見てみましょう。 底の変換公式を使用すると $${\log_8N}$$ は以下のように変換できます。

$$
\begin{array}{} log_8N &=& \frac{\log_2N}{\log_28} \\ &=& \log_2N\times\frac{1}{3}\end{array}
$$

3倍の差になりました。 一般的に計算量を考えるとき、定数倍の値は大した変化にならないため無視します。 対数の底も定数倍の違いにしかならないので無視すると、無事に $${\log N}$$ の形になりました！！

どんなアルゴリズムだとlogになるの？

暴論となりうる可能性はありますが、2や10で元のデータを繰り返し割るようなアルゴリズムは、
計算量 $${\log n}$$ になる！くらいのイメージを持っていいのではないでしょうか。
(審議)

例えば任意の数字の各桁に特定の数字が含まれるかをチェックする操作は、
10で割ったあまりを検査するということを繰り返す事になりがちで、
その場合の計算量は、 $${\mathcal{O}(\log_{10} n)}$$ になりますが、定数倍の底を無視して $${\mathcal{O}(\log n)}$$ になります。

まとめ

これでもうlogは怖くない！