うごく基本情報

平成27年度 春期 問6

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

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

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

正解と解説を見る

正解:ア

覚えること:2分探索の計算量 = O(log n)。線形探索 = O(n)、単純なソート = O(n²)、高速なソート = O(n log n)。

2分探索は1回ごとに探す範囲が半分になるので、計算量は log n に比例します(ア)。n は線形探索、n² はバブルソートなど、n log n はクイックソートなどの平均の計算量です。

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