バブルソートの最悪計算量
要素数 n の配列に対するバブルソートの最悪計算量(オーダ)はどれか。
解説を見る
バブルソートは隣接要素の比較・交換を二重ループで行うため、最悪でおよそ n×n 回の比較が必要で計算量は O(n^2)。
誤答の解説
AO(n) は1回の走査で済む線形処理の計算量。
BO(n log n) はマージソートやクイックソート(平均)などの効率的な整列。
DO(2^n) は部分集合の全列挙など指数時間の処理。
ヒント
・二重ループになる整列は n の2乗に比例する。