うごく基本情報

平成21年度 春期 問7

アルゴリズムとプログラミング › 探索アルゴリズム △ ときどき出る

出典:平成21年度 春期 基本情報技術者試験 午前 問7 の問題

出典:平成21年度 春期 基本情報技術者試験 午前 問7

正解と解説を見る

正解:ア

覚えること:2分探索の比較回数は約 log₂n 回(範囲を半分ずつ絞るから)。線形探索は平均 n/2 回。

2分探索は1回の比較で探す範囲を半分にするので、n 個のデータでは約 log₂n 回の比較で見つかります(ア)。n に比例する(ウ)のは線形探索です。イの (log₂n + 1) / 2 は、線形探索の平均比較回数 (n + 1) / 2 と混ぜてしまった式です。エの n² は、単純な整列(バブルソートなど)の比較回数の目安です。

解説はこのサイトが作成したものです。