「二分探索の計算量も分からんヤツw」とマウントを取られた時に見るメモ

本当の本当にただの自分向けのメモです。メモだけど、見られて困る内容じゃない。なら、他の人も見れる方がよい。そんな思考でブログにしている。

書くのはSNS界隈では定期的にマウント取りに使われる*1二分探索の計算量について。定期的に忘れてはいちいち理屈から考えるを繰り返している*2ので、もうメモにしておくことにする。ちなみに結論だけ言うと二分探索の計算量は $\log n$ だ。

指数と対数

二分探索の計算量を考えるにあたってこれが必要。いや、それ抜きにしても指数対数は重要なんだがそれはおいておき…なんで指数と対数が出てくるかというと、二分探索の計算量は対数的に増加するからだ*3。そして対数を説明するにはセットで指数を説明する必要がある。なのでこの順番で説明する*4。

それぞれひとことで説明するとこんな感じ。さすがに指数は分かるだろう。が、普段意識しない対数は忘れがち。

指数 = xをk回かけたらnになる。n = x^k

対数 = xがnになるにはk回掛ける*5。 k= $\log_{x} n$

つまり、指数も対数も考えてることはxにkを掛けることなのだ。それを指数はnから見ていて、対数はkから見ているだけ。

そして指数の場合はk(掛ける回数)が増えるとnがどんどん大きくなる。逆に対数の場合はnがどれだけ増えてもkはそれほど増えない。これはグラフで書くとよくわかる*6。以下は先の数式をx=2, kを0~10の範囲で増加させた場合のグラフだ。なんかこんなグラフ高校二年生くらいの頃に見たよね。

二分探索

ソート済みのデータ列があったとする。この中から目標の値を探すのが二分探索だ。

方法はシンプルで、常に中央の値を確認しながら、探索範囲を半分に絞っていく。

例えば、以下のような昇順の配列を考えよう。

[1, 3, 5, 7, 9, 11, 13, 15]

このような配列に対して9を効率的に探索する方法を考える。

中央（インデックス 3 の値 7）を見る → 7 < 9 なので右側に絞る → [9, 11, 13, 15] が新しい探索範囲（半分に縮小）
次の中央（インデックス 5 の値 11）を見る → 11 > 9 なので左側に絞る → [9] が新しい探索範囲（また半分に縮小）
残った 9 を確認 → 見つかった！

となる。今回は8つしか数値がないので前から見ても後ろから見てもすぐに見つかる。が、これが1000000個の数値とかが一意に並んでると順番に見ていく方法は効率が悪い。なので二分探索という方法が有効になる。具体的にどのくらい差が出るのかはこのあと実際に計算量を比較する。

二分探索の計算量を考える

先の例を使ってn=8のとき、前から見る方法と二分探索する方法で計算量を比較する。

まず前から見た時だが、最悪の場合を想定するとn番目に見つかることになるので計算量はO(n)だ。

一方で二分探索の場合、探索範囲は以下のように変化する。

n/2 (もとの半分を探す。n=8のとき、4つを探すことになる)
n/4 (さらに半分を探す。n=8のとき、2回目では2つを探すことになる)
n/8 (さらに半分を探す。n=8のとき、ここで残った1つに行き当たる)

つまり、もともとn個あるデータが1個になるまでk回半分にしていくってことだ。

これを一般化するとn/2^k=1となる。さらにこの式を解くとn= $2^{k}$ となる。

二分探索の計算回数はnが幾つであろうが2で割る回数(=k)で決まる。だから二分探索の計算量は実質kで評価されることになる。しかし先に前から見た時の計算量はnで表現しているため、今回もnを使って表現したい。そのために対数で表現する必要がある。対数で表現するとk= $\log_{2} n$ となる。計算量を考える場合2という固定値は無視できるため、最終的に計算量はO( $\log n$ )となる。