応用情報技術者 2013年 春期 午前2 問05

探索表と最適探索法【午前2解説】

正解の理由

• aは「コード順に格納」されているので、データが昇順（または降順）に整列しており、中央値から探索範囲を半分に絞っていく2分探索が最適です。
• bは「コードの使用頻度順に格納」されているため、コード順で整列されておらず2分探索は使えません。一方で、使用頻度が高いコードほど表の上位に集中するため、線形探索（先頭から順に探す）が期待平均コストを小さくできます（頻度局在性を利用）。
• cは「コードから一意に決まる場所に格納」されており、コード→位置が直接決定できるためハッシュ表探索（直接アドレス法やハッシュ法）が最適です。

解法ステップ

1. 各表の格納規則を整理する
   • a: コード順（整列済み）
   • b: 使用頻度順（コード順ではない）
   • c: コードで一意に位置が決まる（直接配置）
2. 整列・非整列の観点で使える探索法を判定する
   • 整列されている→2分探索が有効（$O(\log n)$）
   • 整列されていない→2分探索は不可（前処理で整列すれば可だがコストがかかる）
3. 使用頻度を活かせるかを判断する
   • 頻度順格納なら線形探索で早期ヒットが期待できる（平均が良くなる）
4. 位置が直接決まる場合はハッシュ／直接アドレスを選ぶ（期待$O(1)$探索）
5. 各表に対して最適な手法を割り当て、選択肢と照合する

選択肢別の誤答解説

• ア（正答）
  a: 2分探索、b: 線形探索、c: ハッシュ表探索。上記の理由で最も合理的な組合せです。
• イ（誤り）
  bをハッシュ表探索にしている点が問題です。bは「使用頻度順」であってコード→位置の関数が与えられているわけではないため、ハッシュ表探索を意味的に想定する条件が満たされていません。ハッシュにするには別途ハッシュ構造を作る必要があり、問いの「格納法に最も適した手法」という観点から外れます。
• ウ（誤り）
  bに2分探索を割り当てていますが、2分探索はデータがコード順に整列されていることが前提です。bは使用頻度順でコード順に並んでいないため適用できません。
• エ（誤り）
  cに2分探索を当てていますが、cはコードから直接位置が決まる配置です。直接位置決定が可能ならハッシュ・直接アドレスで$O(1)$が期待でき、わざわざ2分探索を使うのは非効率です。

よくある誤解

• 「頻度順でも2分探索が使える」
  頻度順に並んでいてもコード順に整列されていなければ2分探索は成立しません。2分探索は検索キーの大小関係に基づく分割が前提です。
• 「ハッシュ表＝常に最速」
  ハッシュ表は平均で高速ですが、ハッシュ関数や衝突処理の選び方、メモリ利用量（直接アドレスでは大きな表が必要）により適用可否や性能が変わります。cのように「一意に決まる」なら直接アドレスが有利ですが、キー空間が巨大なら実装上の工夫が要ります。

補足コラム

• 各探索法の代表的な時間計算量（nは要素数）
  • 2分探索（整列済み配列）：検索 $O(\log n)$、挿入/削除は$O(n)$
  • 線形探索（未整列）：平均 $O(n)$（ただし頻度局在なら平均短縮）
  • ハッシュ表（平均）：検索 $O(1)$、最悪は衝突で$O(n)$（衝突処理による）
• 「cの配置」は厳密には直接アドレス法（キーが小さな整数であれば配列のインデックスとして使う）に該当します。ハッシュ表はキー空間が大きいときに配列サイズを節約するための一般化で、衝突処理（チェイニングや開番地法）が必要です。

• Q: b表をコード順に再整列すれば2分探索が可能ですか？
  A: はい。ただし再整列のコスト（$O(n\log n)$など）を考慮すると、検索頻度が高いなら頻度順のまま線形探索の方がトータルで有利な場合があります。
• Q: cがすべて空きスロットを含む場合でもハッシュ表で良いですか？
  A: cは「コードから一意に場所が決まる」点が重要です。空きスロットが混在していても、コード→位置関数があれば直接アドレス/ハッシュで探索できます。空きが多いとメモリ効率に注意してください。
• Q: 実務ではどの指標で選べばよいですか？
  A: 検索回数（読み出し頻度）、挿入／削除頻度、メモリ制約、キー空間の性質（密か疎か）を総合して選びます。