問題
クイックソートの平均計算量と最悪計算量の組合せとして正しいものはどれか。
選択肢
- 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問を繰り返し学習