平成21年度 春期 問7
アルゴリズムとプログラミング › 探索アルゴリズム △ ときどき出る
出典:平成21年度 春期 基本情報技術者試験 午前 問7
正解と解説を見る
正解:ア
覚えること:2分探索の比較回数は約 log₂n 回(範囲を半分ずつ絞るから)。線形探索は平均 n/2 回。
2分探索は1回の比較で探す範囲を半分にするので、n 個のデータでは約 log₂n 回の比較で見つかります(ア)。n に比例する(ウ)のは線形探索です。イの (log₂n + 1) / 2 は、線形探索の平均比較回数 (n + 1) / 2 と混ぜてしまった式です。エの n² は、単純な整列(バブルソートなど)の比較回数の目安です。
解説はこのサイトが作成したものです。