2012年12月23日日曜日

=== 平成24年秋 問3 ===


平成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回の探索で済む。





にほんブログ村 IT技術ブログ IT技術情報へ
にほんブログ村