のさまざまな実装の予想実行時間と最悪の場合の実行時間の両方を知っている人はいstd::nth_elementますか？私はこのアルゴリズムをほぼ毎日使用しています。
最近のMicrosoftコンパイラに同梱されているSTLバージョンに特に興味がありますが、このトピックに関する情報は役に立ちます。
これはこの質問の複製ではないことに注意してください。どのアルゴリズムが存在するかは理解していますが、どの実装がどのアルゴリズムを使用しているかに興味があります。
背景として、これを行うためのよく知られたアルゴリズムがあります。1つはO（n）平均ケースとO（n log n）ワーストケースで、もう1つはO（n）ワーストケースですが、実際には遅いです（中央値の中央値）。また、実際には高速な最悪の場合のO（n）実行時間を取得するための興味深い実装戦略の話があることにも注意してください。標準では、これはO（n）平均時間よりも悪いはずであるとされています。
予想される実行時間は O(N) です。ほとんどの実装では QuickSelect を使用しており、QuickSelect が不適切なパーティションで実行される可能性があるため、ほとんどの実装で最悪の場合の実行時間は O(N * N) です。これは、Microsoft VS2008、VS2010、および VS2012 に当てはまります。
現在、新しい ISO C++ 2011 標準では、std::sort の複雑さが引き締まっています。O(N * log N) であることが保証されており、David Musser の IntroSort が使用されているため、最悪のケースはありません: - QuickSort を使用し、配列の一部で不適切なパーティショニングが発生し、ヒープソートにスワップします。
理想的にはまったく同じことが std::nth_element に適用されるべきですが、ISO C++ 2011 標準は複雑さの要件を強化していません。したがって、std::nth_element は最悪の場合 O(N * N) になる可能性があります。これは、David Musser の元の論文 (ここを参照) で、QuickSelect がうまくいかなかった場合にどのアルゴリズムに切り替えるかについて言及していないことが原因である可能性があります。
最悪の場合、5 のグループを使用した中央値の中央値を使用できます (7 のグループを推奨する論文を見たことがありますが、見つかりません)。そのため、std::nth_element の高品質な実装では、QuickSelect を使用して、パーティショニングがうまくいかない場合に median-of-medians にスワップできます。これにより、O(N) の動作が保証されます。QuickSelect は、サンプリングを使用して最悪のケースを起こりにくくすることで改善できますが、不可能ではありません。
cppreferenceによると、最初に並べ替えてから n 番目の要素を見つけますが、この方法では (比較ベースの並べ替えアルゴリズムによって) 平均になるはずですO(n log n)が、平均は O(n) であると書かれています。しかし、一般的な比較ベースの入力があるため、基数ソートまたは比較ベースではないその他のソートを使用することは不可能のようです。とにかく、高速ソートアルゴリズムを使用することは、実際には通常の選択アルゴリズムを使用するよりも優れています (メモリと平均時間の両方)。