[計算量をざっくり理解] 2分探索の計算量

線形探索とは 線形探索(せんけいたんさく、英:linear search, sequential search)は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。 ...

2分探索

二分探索(にぶんたんさく、: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ソートされている配列の探索は、線形探索ではなく2分探索を使うことで、計算量を減らすことができます。

探索の時に、最初から値を見るのではなく、まずは中央の値を見て、目標との大小関係により、目標が中央の値の右にあるか、左にあるかを判断することで、存在しないほうの半分のデータを省いていきます。

例えば、以下のような配列を考えます。

1351112131722252830

この配列で「3」を2分探索してみます。

まずは、中心の「13」を見ます。目標の「3」は「13」より小さいので存在するならば左半分に存在するはずです。よって、次は以下のような配列を2分探索します。

1351112

これを、目標が見つかるか、配列の個数が1個になるまで続けます。

2分探索の計算量を考えます。

N個の配列を考えた時、一度の探索で探索範囲が半分になり、配列の個数が1になるまで探索を続けるので、探索回数を\(x\)と置いて、以下のように立式して解きます。

\( 1 = \displaystyle \frac { N } { 2^x } \)

\( 2^x = N \)

\( \log 2^x = \log N \)

\( x = \log N \)

よって、2分探索は、\( O ( \log N ) \) の対数 Logarithmic の実行時間となります。

これは、例えば、「配列の個数が4倍になったときは2倍の実行時間が必要になる」ことを意味しています。

線形探索の場合は 「配列の個数が4倍になったときは4倍の実行時間が必要になる」ことと比較すると、2分探索の計算量は少なくなります。

バブルソート バブルソート(bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば...