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

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

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

【平成16年春 問11】


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