平成24年秋期基本情報技術者午前問3

探索方法とその実行時間のオーダの適正な合せはどれか。
ここで、探索するデータ数をn とし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。
また、実行時間のオーダがn²であるとは、n個のデータを処理する時間がcn²(c は定数)で抑えられることをいう。

答え　ア

【解説】
探索には以下のような方法がある。

2分探索
ソート済みのリストや配列の形になっているデータの中央の位置にある値を調べて、探している値より大きいか小さいかで、次に探索する領域を決め、その領域に対し繰り返し適用するアルゴリズムであり、処理時間のオーダはlog₂n である。
線形探索
リストや配列の形になっているデータを先頭から1つ1つ調べて、見つかれば終了するアルゴリズムであり、処理時間の平均値はn/2になり、オーダはn である。
※線形探索は未整列のデータに対しても適用可能である。
ハッシュ探索
整列は、データからハッシュ関数でキー値を求め、そのキー値で格納する位置を決め整列を行う。
探索は、探しているデータのキー値をハッシュ関数で求め、そのキー値を格納する位置を調べることでデータを探すアルゴリズムで、処理時間のオーダは1である。
複数のデータで同じキー値になることを衝突といい、そのときのデータ格納位置の決め方も別途定義する必要がある。

平成24年 秋期 基本情報技術者 午前 問3