問題
クイックソートのアルゴリズムにおける平均計算量と最悪計算量の組合せとして正しいものはどれか。
選択肢
- 1平均 O(n log n) / 最悪 O(n log n)
- 2平均 O(n log n) / 最悪 O(n²)
- 3平均 O(n²) / 最悪 O(n²)
- 4平均 O(n) / 最悪 O(n log n)
正解
2. 平均 O(n log n) / 最悪 O(n²)
詳しい解説を見る解説を閉じる
解説
クイックソートは分割統治法により平均 O(n log n) で動作するが、ピボット選択が悪い（既にソート済みのデータで端をピボットに選ぶなど）と分割が偏り、最悪 O(n²) となる。マージソートとヒープソートは最悪でも O(n log n) を保証する。
一問一答
全400問を繰り返し学習