問題
クイックソートの平均計算量と最悪計算量の組合せとして正しいものはどれか。
選択肢
- 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²)になる（既ソート配列に対し最初の要素をピボットにする場合など）。ランダムピボットなどで最悪ケースを回避できる。
一問一答
全400問を繰り返し学習