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

解説

バブルソートは隣接要素を比較し、大小が逆なら交換する操作を繰り返す整列法である。要素数nのとき、1回目の走査で n-1 回、2回目で n-2 回と比較が続き、合計は (n-1)+(n-2)+…+1 = n(n-1)/2 回となる。これはnの2乗に比例するため最悪計算量はO(n^2)であり、エが正解である。アのO(log n)は二分探索の計算量、イのO(n)は線形探索、ウのO(n log n)はクイックソート・マージソート・ヒープソートなど高速な整列法の平均計算量である。アルゴリズムと計算量（オーダ記法）の対応は科目Aの最頻出事項であり、単純整列はO(n^2)、高速整列はO(n log n)という組をセットで暗記しておきたい。