アルゴリズム・プログラミング定義問題
時間計算量O(n log n)として知られる代表的なソートアルゴリズムはどれか。
A.バブルソート
✗ バブルソートの平均・最悪時間計算量はO(n²)です。O(n log n)ではありません。
B.選択ソート
✗ 選択ソートの時間計算量はO(n²)です。比較回数が常にn(n-1)/2回となります。
C.マージソート← 正解
✓ 正解です。マージソートは分割統治法を用い、平均・最悪ともにO(n log n)の時間計算量を持ちます。
D.挿入ソート
✗ 挿入ソートの平均・最悪時間計算量はO(n²)です。ただし最良ケースはO(n)です。