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