問題プレビューID: 4c51d423

問 3

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

	2分探索	線形探索	ハッシュ探索

解説

2分探索：探索範囲を半分ずつ絞り込むため，最悪の場合の実行時間のオーダは $O(\log_2 n)$ である。
線形探索：先頭から順に調べるため，最悪の場合の実行時間のオーダは $O(n)$ である。
ハッシュ探索：ハッシュ値から格納位置を直接計算でき，衝突を無視できるので $O(1)$ である。

したがって，組合せ $(\log_2 n,\ n,\ 1)$ となる「ア」が正解である。