修了試験 2016-01-24実施分 基本情報技術者試験 問4

解説

正解は1です。 この問題は、代表的な探索方法の実行時間のオーダ（計算量）を問うています。 2分探索は整列済みのデータを半分ずつ絞り込むので、比較回数はおよそlog_2 n回です。 線形探索は先頭から順に調べるので、最悪でn回の比較が必要で、オーダはnです。 ハッシュ探索は、衝突を無視できればハッシュ値の計算で格納位置が直接決まるので、オーダは1（定数）です。 【選択肢別解説】 1：○ 2分探索がlog_2 n、線形探索がn、ハッシュ探索が1で、すべて正しい組合せです。 2：× n log_2 nは、クイックソートなどの高速な整列の平均的なオーダです。 2分探索はlog_2 n、ハッシュ探索はlog_2 nではなく1です。 3：× 2分探索はn log_2 nではなくlog_2 nです。 線形探索もn^2ではなくnです。 4：× 2分探索はn^2ではなくlog_2 n、線形探索は1ではなくn、ハッシュ探索はnではなく1です。 【ポイント】 探索は「線形n、2分log n、ハッシュ1」です。 整列は「単純な整列n^2、高速な整列n log n」とセットで覚えると混同しにくくなります。