探索方法とその実行時間のオーダの適正な合せはどれか。
ここで、探索するデータ数をn とし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。
また、実行時間のオーダがn2であるとは、n個のデータを処理する時間がcn2(c は定数)で抑えられることをいう。
| 2分探索 | 線形探索 | ハッシュ探索 | |
| ア | log2n | n | 1 |
| イ | n log2n | n | log2n |
| ウ | n log2n | n2 | 1 |
| エ | n2 | 1 | n |
答え ア
【解説】
探索には以下のような方法がある。
- 2分探索
ソート済みのリストや配列の形になっているデータの中央の位置にある値を調べて、探している値より大きいか小さいかで、次に探索する領域を決め、その領域に対し繰り返し適用するアルゴリズムであり、処理時間のオーダはlog2n である。 - 線形探索
リストや配列の形になっているデータを先頭から1つ1つ調べて、見つかれば終了するアルゴリズムであり、処理時間の平均値はn/2になり、オーダはn である。
※線形探索は未整列のデータに対しても適用可能である。 - ハッシュ探索
整列は、データからハッシュ関数でキー値を求め、そのキー値で格納する位置を決め整列を行う。
探索は、探しているデータのキー値をハッシュ関数で求め、そのキー値を格納する位置を調べることでデータを探すアルゴリズムで、処理時間のオーダは1である。
複数のデータで同じキー値になることを衝突といい、そのときのデータ格納位置の決め方も別途定義する必要がある。
【キーワード】
・探索方法
- 探索方法
この問題での『探索』はデータの中から、目的のデータを探し出す方法である。
探索方法(アルゴリズム)には、問題の2分探索、線形探索、ハッシュ探索以外にもあるが、この3つのアルゴリズムを把握しておけば十分である。
どの探索方法を使うかはデータが整列されているか、整列されている場合はどういった整列方法を行ったかで変わってくる。
もっと、「探索方法」について調べてみよう。
戻る
一覧へ
次へ