平成24年秋目次 前の問題 次の問題
問3
探索方法とその実行時間のオーダの適切な組み合わせはどれか。ここで、検索するデータの数をnとし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また、実行時間のオーダがn2であるとは、n個のデータを処理する時間がcn2(cは定数)で抑えられていることをいう。解説
■2分探索の場合たとえば1024個のデータがあったとすると、真ん中の値を1回比較することで半分に絞られるとすると、2回目で1/4、3回目で1/8・・・10回目で1/1024となるはず。
log21024=10となるので、log2nが正解
■線形探索の場合
最初からすべて見ていくため、n個のデータがあればn回比較すればよいことになるため、nが正解
■ハッシュ探索の場合
ハッシュ値とは、データから計算した値であり、それによりデータの置き場所を決めることになる。
同じ値になる確率は無視できるほど小さいといっているので、データからハッシュ値を1回計算すれば、その場所にそのデータがあるため、1回の探索で済む。
答
アにほんブログ村