平成18年秋期試験問題 午前問14
広告
解説
探索アルゴリズムに関する問題は頻出です。それぞれの特徴を覚えておきましょう。
- 線形探索法
- 探索対象のデータ群の先頭から順に値を比較していく方法。データ群が整列されていなくても探索できるが、使用頻度が高い順に整列されていると少ない回数で目的のデータを探索することが可能になる。
平均比較回数:(N＋1)／2，最大比較回数:n - 2分探索法
- 探索データが昇順または降順に整列されているときに用いる方法。データ中央値と探索対象のデータを比較し、その大小により探索範囲を1／2ずつ狭めていくことで線形探索と比べて効率よく探索することが可能。
平均比較回数:[log2N]，最大比較回数:[log2N]＋1
(※[a]はaを超えない最大の整数を表します)
広告