修了試験 2017-07-23実施分 基本情報技術者試験 問4

解説

正解は1です。 探索の実行時間のオーダは、データ数nが増えたときに処理時間がどの程度増えるかを表します。 2分探索は1回の比較で探索範囲が半分になり、線形探索は先頭から順に比較します。 ハッシュ探索は、キーから計算したハッシュ値で格納位置を直接求めます。 【選択肢別解説】 1：○ 2分探索は範囲を半分ずつ絞るので、比較回数は log_2 n に比例します。 線形探索は最悪n回比較するのでnです。 ハッシュ探索は衝突がなければ1回の計算で位置が分かるので、データ数によらず一定（オーダ1）です。 2：× 2分探索を n log_2 n、ハッシュ探索を log_2 n としている点が誤りです。 n log_2 n はクイックソートなどの高速な整列の平均的な計算量です。 正しくは2分探索が log_2 n、ハッシュ探索が1です。 3：× 2分探索の n log_2 n と、線形探索の n^2 が誤りです。 n^2 はバブルソートなどの単純な整列の計算量です。 正しくは2分探索が log_2 n、線形探索がnです。 4：× 3つとも誤りです。 線形探索をオーダ1、ハッシュ探索をnとしていますが、実際は線形探索がn、ハッシュ探索が1です。 2分探索も n^2 ではなく log_2 n です。 【ポイント】 探索は「ハッシュ 1 ＜ 2分 log n ＜ 線形 n」、整列は「高速な整列 n log n ＜ 単純な整列 n^2」と、探索と整列を区別して覚えましょう。 なお、2分探索はデータが整列済みであることが前提です。