探索アルゴリズム

このページでは、線形探索・番兵法・2分探索の手順と比較回数、ハッシュ法とシノニムの対策、計算量を表すオーダ記法がわかります。

一言で言うと：
- たくさんのデータの中から目的のデータを探す3つの方法（端から順に、半分ずつ、場所を計算して一発で）と、その速さを表す「オーダ」の話。

端から順に探す（線形探索法、番兵法）→ 半分ずつ絞る（2分探索法）→ 場所を計算する（ハッシュ法）→ 速さの物差し（オーダ）

覚え方の軸
線形探索法と2分探索法：端から順か、半分ずつか
ハッシュ法：キーから格納場所を計算する
オーダ（order）：O記法
混同しやすいペア

覚え方の軸

3つの探索法は「1回の比較でどれだけ絞れるか」で並ぶ：
- 線形探索は1個ずつ（O(n)）、2分探索は半分ずつ（O(log n)）、ハッシュは計算で一発（理想はO(1)）
前提条件の違い：
- 線形探索は並んでいなくてもよい、2分探索は整列済みが必要、ハッシュはハッシュ関数が必要
ハッシュは「ぶつかったとき（シノニム）にどうするか」で2つ：
- 空いている隣を探す（オープンアドレス法）、リストでつなぐ（チェイン法）
オーダは「一番増え方の大きい項だけ残す」：
- O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)

線形探索法と2分探索法：端から順か、半分ずつか

線形探索法（逐次探索法）：
- 探索対象データの先頭から順に探す
- データがn個のとき、最小比較回数は1回、最大比較回数はn回、平均比較回数は （n＋1）／2回
- nが十分大きいときの平均比較回数は n／2 と考える
- 計算量のオーダは O(n)
  - 意味：
    - 探索にかかる時間が、データの個数nに比例する
オーダ：
- アルゴリズムが答えを出すまでに、どれくらいの計算時間が必要かを表す概念（後の「オーダ」で詳しく扱う）
番兵法：
- 線形探索の終了判定は、ふつう「見つかったか」と「最後まで探したか」の2つ。比較のたびに2つ判定するのは時間の無駄
- そこで、探すデータと同じデータ（番兵）を末尾に追加し、終了判定を「見つかったか」だけにする
- 例：
  - 6 2 9 4 7 3 の末尾A［7］に、探すデータ5を番兵として置く。A［1］〜A［6］になくても、A［7］で必ず一致する（A［7］で見つかったら「データはなかった」と判断する）
- 番兵を使っても計算量のオーダは変わらないが、終了判定が1つになって実行ステップ数が減るので、実際の速度は上がる
2分探索法：
- 大小比較を使う探索法の中で、一番シンプルなもの
- 昇順か降順に整列されたデータにしか使えない
- 整列されたデータの中央の位置midの値（中央の値）と探すデータを比べる
  - 探すデータ＞中央の値：
    - 次はmidより右を探す
  - 探すデータ＜中央の値：
    - 次はmidより左を探す
- 1回の比較ごとに探索範囲が1／2になるので、n個ならlog₂n回比べれば範囲が1以下になって終わる
- 計算量のオーダは O(log₂n)。底の2を省略して O(log n) と書くことが多い
- log₂nになる理由：
  - データが1つになるまでの比較回数をaとすると 2ᵃ＝n。2を底とする対数をとって a＝log₂n
線形探索法との比較：
- 一般に2分探索法の方が効率がよい
- 例：
  - 整列された1,000個のデータなら、線形探索は平均で約500回、2分探索は約10回
  - log₂1,000＝log₂10³＝3×log₂10 ≒ 3×3.32＝9.96
- 注意：
  - 2分探索法がいつも速いとは限らない。探すデータが先頭にあれば、線形探索の方が断然速い

	線形探索法	2分探索法
前提	並んでいなくてよい	整列済みであること
最大比較回数	n回	約log₂n回
平均比較回数	（n＋1）／2回	約log₂n回
オーダ	O(n)	O(log n)

例題：
- 整列済みの1,024件から探す
- 線形探索の平均比較回数：
  - （1,024＋1）÷ 2 ≒ 512回
- 2分探索の最大比較回数：
  - log₂1,024＝10回（1,024＝2¹⁰）

ハッシュ法：キーから格納場所を計算する

ハッシュ法：
- 探すデータのキー値から、データの格納場所（アドレス）を直接計算する方法
- 長所：
  - 一意探索（1件を探す）に優れていて、線形探索法や2分探索法より探索時間が短い
- 短所：
  - 連続したデータの探索（範囲の探索）には向かない
ハッシュ関数：
- 格納場所の計算に使う関数
ハッシュ値（ハッシュアドレス）：
- キー値からハッシュ関数で求めた値
値域：
- ハッシュ関数から得られる値の範囲
衝突（シノニムの発生）：
- 異なるキー値から、同じハッシュ値が求められること
- 理想は「異なるキーから同じハッシュ値は出ない」ことだが、実現は難しい。どんなハッシュ関数を使っても、シノニムの発生は防げない
シノニム：
- 衝突が起きて、本来入れるべき場所に入れられないデータ
ホーム：
- その場所に先に入っているデータ
シノニムを最少にするには、ハッシュ値が偏らない一様分布になるようなハッシュ関数を選ぶ
探索時間とデータ数の関係（★試験では「データ数と探索時間の関係を表すグラフ」が問われる）
- シノニムが発生しないなら、データ1個あたりの探索時間は、データの個数に関係なく一定（横一直線のグラフ）
- シノニムが発生するなら、探索時間は格納領域の使用率に左右される
例題：
- ハッシュ関数を「キー値を5で割った余り」とする
- キー12 → 12÷5＝2余り2、キー17 → 17÷5＝3余り2
- どちらもハッシュ値2なので衝突（シノニム）が起きる
シノニムが起きたときの対策は2つ
オープンアドレス法：
- シノニムが起きたら、別のハッシュ関数で再ハッシュする
- 一般には「求めたハッシュ値＋1」を新しいハッシュ値にし、空いていればそこに入れ、空いていなければ同じ操作で次を探す。最後まで行っても見つからなければ先頭に戻って探す
- ハッシュ表は環状につながっていると考えて後ろの空きを順に探す。空き要素が1つだけになったら、格納せずにオーバフローとする
- 上の例題なら、キー17はハッシュ値2が埋まっているので、2＋1＝3番に入れる
- クラスタリング：
  - 使用中の要素が連続する現象
- 問題点：
  - 要素番号3〜6が連続して埋まっていると、6番のデータは本当はハッシュ値3〜5のデータが後ろにずれて入ったものかもしれない
  - 全部ハッシュ値3なら、途中の5番を削除すると、6番のデータが探索できなくなる（3から順に見ていって、空いた5番で「ない」と判断してしまう）
  - そのため削除したときは、探せなくなるデータを1つずつ前にずらす処理が必要
チェイン法（チェーン法、連鎖法）：
- 同じハッシュ値をもつデータを、ポインタでつないだリストとして格納する
- 例：
  - データPとデータQが同じハッシュ値5なら、ハッシュ表の5番にはPへのポインタを入れ、QはPの次にポインタでつなぐ
チェイン法の探索の計算量：
- 全データ数N、ハッシュ表の大きさM、各リストの長さがほぼN／M個とする
- ハッシュ値hを求め、ハッシュ表［h］（ハッシュ表のh番目の要素）が指すデータからリストを順にたどる
- 比較回数は最小1回、最大N／M回。計算量はN／Mで決まる
- Mが大きければ計算量は少なく、小さければ多い
- Mを、データ数Nに対して十分大きくすれば、計算量は最良のO(1)になる
- 例：
  - N＝1,000件、M＝100なら、1本のリストは約10件なので、最大で約10回の比較

	オープンアドレス法	チェイン法
衝突したら	再ハッシュ（一般に＋1）して空きを探す	同じハッシュ値のデータをリストでつなぐ
格納場所	ハッシュ表の中だけ	ハッシュ表＋リスト
注意点	クラスタリング、削除時に前へずらす処理が必要	計算量はN／Mで決まる

オーダ（order）：O記法

オーダ：
- アルゴリズムの評価に使う計算量の表し方の一つ
計算量の種類
- 時間計算量：
  - 答えを出すまでにどれくらいの時間がかかるか
- 領域計算量：
  - どれくらいの領域（メモリ）が要るか
- 単に「計算量」といったら、時間計算量のことが多い
オーダ記法：
- データ数nが増えると計算量がどう増えるか、上限はどれくらいか、という計算量の概要（漸近的な振舞い）を、O（ビッグオー）の記号で表す
- 計算量をnの関数で表し、定数や係数を除き、nについて最も速く増える項だけで評価する
- 例：
  - f(n)＝2n²＋5n＋3 なら O(n²)
  - g(n)＝log₂n なら O(log n)
  - O(n²)とO(log n)の2つの部分からなるなら、全体はO(n²)＋O(log n)だが、O(n²)に簡略化する
大小関係（覚える）：
- O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)
オーダを求める2つの規則
- 規則1（順次処理）：
  - 順に並んだ部分は、大きい方のオーダが全体のオーダになる
- 規則2（繰返し処理）：
  - 繰り返す部分のオーダに繰返し数を掛けたもの（定数は無視）が全体のオーダになる
- 例：
  - O(n)の処理をn回繰り返すなら O(n²)。O(log n)の処理をn回繰り返すなら O(n log n)
例題：
- n＝1,024のときの目安
- log₂n＝10、n＝1,024、n log₂n＝10,240、n²＝1,048,576（約100万）
- オーダが1つ上がると、計算量が大きく変わることがわかる

混同しやすいペア

線形探索法（先頭から順、O(n)、整列不要）／2分探索法（半分ずつ、O(log n)、整列が必要）
平均比較回数：
- 線形探索は（n＋1）／2（nが大きければn／2）、2分探索は約log₂n
番兵法（実行ステップ数が減る）／オーダ（番兵法を使っても変わらない）
シノニム（衝突して入れない側のデータ）／ホーム（先にその場所に入っているデータ）
オープンアドレス法（＋1して空きを探す）／チェイン法（リストでつなぐ、連鎖法）
時間計算量（時間）／領域計算量（メモリ）
ハッシュ法の得意（一意探索）／不得意（連続したデータの探索）

← 02 アルゴリズムとプログラミングの目次に戻る