たくさんのデータの中から目的の1件を見つけ出すのが「探索アルゴリズム」です。線形探索・二分探索・ハッシュ探索の違いと、計算量(オーダー)の考え方を、身近な例で整理しましょう。
星見 めい
ねえ先生、データを探すのって、上から順番に見ていく以外にやり方あるの?
紫垣 こはる 先生
いい質問ね。
実はその「上から順番」が、最も基本的な探索なのよ。
名前もちゃんとあるの。
紫垣 こはる 先生
それが線形探索。
出席番号順に名前を呼んで、目当ての人がいるか1人ずつ確かめる感じね。
小夜川 ほのか
あー、それなら誰でもやってますねぇ。
確実だけど…人数が多いと大変そうですぅ。
蜂谷 まこと
そこを速くしたのが二分探索です。
ただし条件があって、データが小さい順(または大きい順)に並んでいることが必須なんです。
星見 めい
並んでないとダメなんだ。
で、どうやって速くするの?
蜂谷 まこと
まん中の値を見て、探したい値がそれより大きいか小さいかを判断します。
それだけで、調べる範囲が一気に半分になるんです。
紫垣 こはる 先生
そう、辞書の引き方とそっくりよ。
『さ』の項目を探すとき、まん中を開いて『た』が出たら、後ろ半分は全部見なくていいでしょう?
小夜川 ほのか
あっ、わかりますぅ!
見なくていい場所がどんどん消えていくんですねぇ。
星見 めい
じゃあさ、10万件あったら比較回数ってどれくらい違うの?
紫垣 こはる 先生
線形探索は運が悪いと最大10万回。
二分探索は半分ずつ削るから、log2(100000)でおよそ17回よ。
星見 めい
17回!?
マジか、10万回と17回って差がエグすぎじゃん。
蜂谷 まこと
その速さの違いを表すのが計算量です。
線形探索はO(n)、二分探索はO(log n)。
nが増えるほど差が開きます。
小夜川 ほのか
じゃあ最初から二分探索を使えばいいんじゃないですかぁ?
蜂谷 まこと
そこが落とし穴で、二分探索は事前にソート(並べ替え)が必要です。
1回探すだけなら、ソートの手間で結局トントンになることもあります。
紫垣 こはる 先生
だから判断基準はこう。
同じデータを何度も探すなら、ソートは最初の1回だけ。
あとはずっと二分探索で速い。
ここがポイントよ。
星見 めい
なるほど、繰り返し探すかどうかで選ぶんだね。
じゃあ、これより速いのはもう無いの?
蜂谷 まこと
あります。
ハッシュ探索です。
値を計算式に通して『この箱にある』と一発で当てる方法で、平均O(1)、つまりデータ量にほぼ関係なく一定時間で見つかります。
小夜川 ほのか
計算で場所がわかっちゃうんですかぁ。
魔法みたいですぅ。
紫垣 こはる 先生
ふふ、便利だけど別の値が同じ箱に当たる衝突が起きることもあるの。
そこは覚えておいてね。
紫垣 こはる 先生
ちなみに木やグラフをたどる探索もあって、幅優先探索と深さ優先探索が代表よ。
星見 めい
幅と深さ…どっちがどっちか混ざりそう。
覚え方ない?
蜂谷 まこと
対比で覚えるといいです。
幅優先(BFS)は近い順に広げるのでキュー、深さ優先(DFS)は奥まで潜って戻るのでスタック。
『広いキュー、深いスタック』と語呂で結びつけましょう。
星見 めい
広いキュー、深いスタック!
これなら忘れないわ。
探索って奥が深いじゃん。
紫垣 こはる 先生
最後に整理するわね。
1件だけなら線形、何度も探すならソート＋二分、一発で当てたいならハッシュ。
場面で使い分けるのがコツよ。
確認クイズ
ソート済みのデータに対して二分探索を行う場合の計算量(オーダー)はどれか。
- O(1)
- O(log n)
- O(n)
- O(n²)
こたえを見る
正解: 2. O(log n)
正解はO(log n)。二分探索は比較のたびに探す範囲を半分に絞るため、データが100万件でも約20回の比較で済みます。O(1)はハッシュ探索(位置を直接計算)、O(n)は線形探索(先頭から順に比較)、O(n²)は単純な並べ替えなどに見られる計算量で、いずれも二分探索には当てはまりません。