基本情報技術者 平成19年秋 問11

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

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


n2
1
エ 
n2
1
n

 

解答を見る