基本情報技術者 予想問題｜A 第15問

解説

正解はウ。マージソートは配列を半分ずつに分割していき（分割の深さはlog n段階）、各段階で全要素を比較しながら併合（マージ）するため、計算量はO(n log n)となる。データの初期の並び方によらず安定してこの性能を保つ点が特徴である。アのバブルソートとイの選択ソートは、二重ループで要素を総当たり的に比較するためO(n²)であり、エの線形探索は先頭から順に1回走査するだけなのでO(n)である。基本情報では整列・探索アルゴリズムの計算量比較が頻出であり、O(n log n)グループ（マージソート・ヒープソート・クイックソートの平均）とO(n²)グループ（バブル・選択・挿入）を区別すること、クイックソートは最悪時O(n²)に劣化する点まで押さえておくと確実である。