基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [平成31年春午前] [平成31年春午後]

平成16年 春期 基本情報技術者 午前 問11
問11   探索方法の実行時間

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

  2分探索 線形探索 ハッシュ探索
ア   log2 n n 1
イ   n log2 n n 2 1
ウ   n 2 1 n
エ   n log2 n n log2 n

解答←クリックすると正解が表示されます

解説

探索方法の実行時間

2分探索とはバイナリサーチとも言われ、線形探索よりデータを探索し易い。
実行時間のオーダ=logn
線形探索とはデータを上から比較し、目的のデータを探索
実行時間のオーダ=n

ハッシュ探索とはデータのアドレスを得る
実行時間のオーダ=1


[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]