問題
要素数 n の配列に対するクイックソートの平均計算量と最悪計算量の組合せはどれか。
選択肢
- 1平均 O(n log n)、最悪 O(n log n)
- 2平均 O(n log n)、最悪 O(n^2)
- 3平均 O(n^2)、最悪 O(n^2)
- 4平均 O(n)、最悪 O(n log n)
正解
2. 平均 O(n log n)、最悪 O(n^2)
詳しい解説を見る解説を閉じる
解説
クイックソートは分割統治法で、ピボットを基準に分割する。ピボットが配列をほぼ等分するとき再帰深さ log n、各レベルで n 比較なので平均 O(n log n)。一方、既にソート済みの配列で先頭ピボットを選ぶなど偏った分割では片側が n-1 個になり最悪 O(n^2) に劣化する。ランダム化やメディアン・オブ・スリー法、イントロソート（最悪時にヒープソートへ切替）で実用上 O(n log n) を保証する。マージソートは最悪も O(n log n) だが追加メモリが必要。
一問一答
全400問を繰り返し学習