[0495] 探索,平均比較回数

平成14年度春期 基本情報処理技術者試験より
探索に要する平均比較回数が最も少ないものはどれか。
2分探索木を用いた探索
衝突の確率が無視できるほど小さいハッシュ表を用いた探索
整列済みの配列を用いた2分探索
重複登録のないリストを用いた線形探索

正解

解説

 選択肢の線形探索,ハッシュ探索,2分木探索,2分探索はいずれも有名な探索アルゴリズムです。まずは,各探索アルゴリズムの特徴を説明していきます。

 線形探索は,データをひとつひとつ順に照合していく探索方法です。アルゴリズムは単純ですが,比較回数が多く,あまり効率的ではありません。データの個数を N とすると,平均探索回数は N/2 となります。

 2分探索は線形探索よりも効率的な探索方法です。バイナリサーチとも呼ばれます。目的のデータを,あらかじめソートされたデータ要素の中央に位置するデータと比較し,その大小関係によって探索範囲を狭めていきます。平均探索回数は,log2 N です。( N = 16 であれば,線形探索では 8回,2分探索では 4回となります )

 2分木探索の探索方法は,2分探索と似ています。2分探索では,あらかじめデータをソートしておきますが,2分木探索ではデータを,節が 2本のツリー構造で保持しておきます。

 ハッシュ探索は,データのキー値からハッシュ値を求め,ハッシュ表と呼ばれる表で該当するデータを探し当てます。下図はハッシュ探索の例です。ハッシュ表では社員データを管理しておきます。ハッシュ値は,社員データのキー値(社員コード)から計算された値です。



 ハッシュ探索で,ハッシュ値が衝突する確率が小さければ,ほとんどのケースで 1回の探索だけで目的のデータにたどり着くことが可能になります。よって,イが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題