配列上に不規則に並んだ多数のデータの中から、特定のデータを探し出すのに適したアルゴリズムはどれか。
ア | 2分探索法 |
イ | 線形探索法 |
ウ | ハッシュ法 |
エ | モンテカルロ法 |
答え イ
【解説】
ア | 2分探索法は昇順(降順)に整列されたデータ(配列、リスト)の探索を行う方法である。 探索するデータの中央の値と探索したい値の大小を比較し、探索したい値が中央の値より大きいか、小さいかを判断して、探索するデータの探索範囲を狭めて探索を行う。 |
イ | 線形探索法は、データの状態にかかわらず採用することができる探索方法で、探索するデータの先頭から順に、探索する値と一致するかを比較していきます。 整列済み、未整列にかかわらず探索可能ですが、整列済みのデータの場合は2分探索法に比べ時間がかかります。(整列済みのデータの場合は、2分探索法を用いたほうがいいです。) |
ウ | ハッシュ法は、ハッシュ関数でデータを格納する場所を決めたハッシュテーブルに対し、探索を行う場合の方法です。 |
エ | モンテカルロ法は乱数を使用して、シミュレーションを行う方法で、曲線で囲まれた面積などを求めるのに使用されます。 |
【キーワード】
・探索法
データの状態 | 探索法 |
昇順・降順の整列データ | 2分探索法 |
ハッシュ整列データ | ハッシュ法 |
未整列データ | 線形探索法 |