基本情報技術者 2012年 秋期 午前（科目A） 問03

探索方法と実行時間の組合せ【午前2 解説】

要点まとめ

• 結論：二分探索は $O({\log }_{2}n)$、線形探索は $O(n)$、ハッシュ探索は平均で $O(1)$（衝突無視）が正解です。
• 根拠：二分探索は探索範囲を半分にするので対数回の比較、線形は逐次走査、ハッシュは計算＋直接参照で定数時間となります。
• 差がつくポイント：二分探索は「整列済み＋ランダムアクセス」が必要、ハッシュは衝突やロードファクタで実測性能が変わります。

正解の理由

よくある誤解

• 二分探索 = $O(n\log n)$ とする誤り：これはソートアルゴリズム（例：マージソート）の計算量と混同したものです。二分探索自体は探索のみで $O(\log n)$ です。
• ハッシュは常に $O(1)$：平均では定数ですが、衝突が極端に多い場合や悪意ある入力では最悪 $O(n)$ になる点を見落としがちです。
• リンクリストで二分探索が $O(\log n)$：連続したランダムアクセスが必要なため、単方向リストでは二分探索は効率的に実装できず $O(n)$ になることがあります。

解法ステップ

1. 各探索法がどのデータ構造／前提（整列・ランダムアクセス・ハッシュ表）を要求するか確認する。
2. その前提下で1回の探索に要する基本操作（比較、配列参照、ハッシュ計算など）を列挙する。
3. 基本操作の回数が入力サイズ $n$ に対してどう増えるかを考え、$O(\cdot )$ を導く。
4. 平均／最悪ケースの区別が必要な場合は問題文の前提（衝突無視など）に従う。
5. 選択肢と照らし合わせて当てはまる組合せを選ぶ。

選択肢別の誤答解説

• ア：正しい。二分探索 $O({\log }_{2}n)$、線形探索 $O(n)$、ハッシュ探索（衝突無視で）$O(1)$ の組合せは理論どおりです。
• イ：誤り。二分探索を $n{\log }_{2}n$ としていますが、これはソート等の計算量で、探索単体は $O(\log n)$ です。ハッシュ探索を ${\log }_{2}n$ とするのも誤りです。
• ウ：誤り。二分探索を $n{\log }_{2}n$、線形探索を $n^2$ と誤って評価しています。線形探索は $O(n)$、二分探索は $O(\log n)$ です。ハッシュは正しく $O(1)$ ですが他が間違いです。
• エ：誤り。二分探索 $n^2$、線形探索 $1$、ハッシュ探索 $n$ と逆転・大幅な誤認がある組合せで、現実の性質と一致しません。

補足コラム

• 対数の底（${\log }_{2}n$ や ${\log }_{10}n$）は定数倍の差でありオーダー記法では無視されます。
• ハッシュ表の実際の性能はロードファクタ（要素数／バケット数）やリハッシュ戦略に依存し、リハッシュは「平均的に」定数時間に含まれる（アマortized cost）。
• 二分探索は必ず「整列済み」のデータに使います。未整列データで探索を高速に行いたければ、事前にソート（$O(n\log n)$）するかハッシュ表を構築（$O(n)$～）します。
• 平衡二分探索木（AVLや赤黒木）は探索 $O(\log n)$、挿入削除も $O(\log n)$。ハッシュ表は挿入削除検索が平均 $O(1)$。

FAQ