修了試験 2021-12-12実施分 基本情報技術者試験 問5

解説

正解は1です。 3つの探索方法について、データ数nに対して実行時間がどう増えるか（オーダ）を問う問題です。 表の並びは「2分探索｜線形探索｜ハッシュ探索」の順です。 【選択肢別解説】 1：○ 2分探索は1回の比較で探索範囲が半分になるので、log_2 nです。 線形探索は先頭から順に調べるのでnです。 ハッシュ探索は衝突がなければ1回の計算で格納位置が決まるので1です。 2：× n log_2 nは、クイックソートなどの高速な整列の平均的なオーダです。 2分探索はlog_2 n、ハッシュ探索は1なので誤りです。 3：× 線形探索はデータを1回ずつ調べるだけなのでnです。 n^2にはなりません。 2分探索もn log_2 nではなくlog_2 nです。 4：× 2分探索はn^2ではなくlog_2 nです。 線形探索は1ではなくn、ハッシュ探索はnではなく1です。 【ポイント】 探索のオーダは「線形探索n、2分探索log_2 n、ハッシュ探索1」が定番です。 n log_2 nとn^2は整列（ソート）のオーダとして出題されるので、混同しないようにします。