- 2017-06-05 (Mon) 23:49
- 一般
O(n log n) の計算量を達成するには常に半分半分にしていきたいので,ピボットは中央値にしたい.ところで中央値を探し出すのは選択アルゴリズムで O(n) で出来る.つまり,クイックソートは常に O(n log n) でできる ……とか言ったら怒られるのだろうか? ピボット選択を O(1) でやる the クイックソートは最悪 O(n^2) だろうけど,そこに O(n) の計算量を掛けてもクイックソートだよね?
ということで,クイックソートが何なのかわからない今日このごろ.
- Newer: ことはじめ