quicksort - クイックソートは O(n^2) 時間で実行されますか?

Question

クイックソートの最悪の場合のランタイムが O(n^2) である理由と、これがまれな理由を説明できる人はいますか?

Answer 1

サイズ n/2 の 2 つのリストに分割するのではなく、ピボットが毎回最悪の方法で選択された場合、サイズ 1 のリストとサイズ n-1 のリストに分割されます。これにより、再帰の深さが n になり、合計時間が n^2 になります。

ピボットは通常ランダムに選択されるため、これはまれです。毎回最悪のピボットを選択する可能性は低く、平均して、ピボットはリストをほぼ半分に分割する傾向があります。

最初の要素を取得するなど、ピボットが非ランダムに選択された場合、特定の入力 (事前に並べ替えられたリストまたは逆に並べ替えられたリスト) によって n^2 のパフォーマンスが強制される可能性があります。