応用情報技術者 2010年 秋期 午前2 問06

探索表の構成法と平均計算量の関係【午前2 解説】

要点まとめ

• 結論：aは2分探索、bは線形探索、cはハッシュ表探索が平均計算量最小である。
• 根拠：aはコード順で整列済みのため2分探索が有効、bは使用頻度順で整列されているが順序は不定で線形探索、cはコードから一意に格納位置が決まるためハッシュ探索が最適。
• 差がつくポイント：探索表の構成方法に応じて適切な探索アルゴリズムを選択し、平均計算量を最小化する理解が重要。

正解の理由

• aの探索表はコード順に整列されているため、2分探索が可能で平均計算量は$O(\log n)$と効率的です。
• bは使用頻度順に並んでいるが、コードの順序は保証されていないため2分探索は使えず、線形探索となり平均計算量は$O(n)$です。
• cはコードから格納位置が一意に決まるため、ハッシュ表探索が可能で平均計算量は$O(1)$と最も高速です。
  以上より、a→2分探索、b→線形探索、c→ハッシュ表探索の組み合わせが最も平均計算量が小さくなります。

よくある誤解

• 使用頻度順に並んでいるbで2分探索ができると誤解しやすいですが、順序が保証されていないため不可能です。
• ハッシュ表は必ず高速と考えがちですが、cのように格納位置が一意に決まる場合に限り効率的です。

解法ステップ

1. 各探索表の構成方法を確認し、整列状態や格納規則を把握する。
2. aはコード順に整列されているため2分探索が適用可能と判断。
3. bは使用頻度順でコード順ではないため線形探索が妥当と判断。
4. cはコードから格納位置が一意に決まるためハッシュ表探索が最適と判断。
5. 各手法の平均計算量を比較し、最も小さい組み合わせを選択する。

選択肢別の誤答解説

• イ：bにハッシュ表探索を割り当てているが、bは使用頻度順で格納位置が一意に決まらずハッシュ探索は不適。
• ウ：aに線形探索を割り当てているが、aは整列済みで2分探索の方が効率的。
• エ：cに2分探索を割り当てているが、cは格納位置が一意に決まるためハッシュ探索が最適。
• ア：正解。a→2分探索、b→線形探索、c→ハッシュ表探索の組み合わせ。

補足コラム

• 2分探索は整列済みのデータに対して有効で、平均計算量は$O(\log n)$です。
• 線形探索は順序が保証されない場合に用いられ、平均計算量は$O(n)$と非効率です。
• ハッシュ表探索はハッシュ関数により格納位置が一意に決まるため、平均計算量は$O(1)$と高速ですが、衝突処理が必要な場合もあります。

FAQ