クイックソートキラー

Question

についてあなたの中には、このかわいい記事につまずいたかもしれない - 本当に面白いです何

\ http://igoro.com/archive/quicksort-killer/定義された敵に対して、（N Nを記録）、彼はOで実行するためにクイックソートを修正する方法です。

クイックソートは、各ステップでピボットとしてメディアン要素を選択することができるため、常に入力シーケンスを完全に2つの半分に分割できます。中央値はO（N）の実行時間で決定論的に見つけることができるため、合計実行時間は常にO（N log N）です。

私の質問は、同じ比較関数を使って、O（N^2）ではなくO（N^2）で実行されますか？

編集：

正確には：私はクイックソートと同様の戦略を使用し、それは一つとして同じ比較関数を使用するパーティションベースの中央値選択アルゴリズムの複雑さに疑問を投げかけていますクイックソートが使用します。この敵とO（N）でどのように動作するのですか？

Answer 1

は、線形時間の中央値探知 アルゴリズムは同じ を使用して終了しません（N^2） の代わりに、O（N）の機能を比較して、Oで実行？

はありません、中央に複雑さを見つけるために、O（N）機能を追加することにより、増加した定数は、それが魅力のないなりその記事の状態として、

O((N+N) log N) == O(2N log N) == O(N log N) 

になります。しかし。

標準的な手法は3のメジアンと呼ばれ、フルメジアンの検索は実際にはそれ以上改善されません。

最悪の場合はクイックソートを使用しないでください。 Shellsortの方が上向きです。