データ構造とアルゴリズム
要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素と比べることを、i を1つずつ進めて繰り返す二重ループ)の計算量はどれか。
- AO(n)
- BO(n log n)
- CO(n²)
答えと解説を見る
正解：C. O(n²)
比べる組の数は (n−1) + (n−2) + … + 1 = n(n−1)/2 で、n = 10 なら45回、n = 1000 なら499,500回です。計算量のオーダーは n が大きくなったときの増え方だけを見るので、係数の1/2や低い次数の項を省いて O(n²) と表します。n が2倍になると回数はおよそ4倍になります。O(n) は全要素を1回ずつ見るだけの処理、O(n log n) はマージソートのように半分に分けることを繰り返す処理の計算量です。
- A. 全要素を1回ずつ見るだけなら O(n) ですが、ここでは要素ごとに残りの要素すべてと比べています。
- B. 半分に分けることを繰り返すマージソートなどの計算量で、すべての組を比べる処理より小さくなります。
- C. 正しい。比較は n(n−1)/2 回で、n² に比例して増えます。