5

中央値の中央値アルゴリズムとは別に、最悪の場合のO（n）時間でk選択を行う他の方法はありますか？中央値の中央値を実装することは理にかなっていますか。つまり、パフォーマンス上の利点は実用的な目的には十分ですか？

4

4 に答える 4

12

ソフトヒープデータ構造に基づいてk次統計を計算するための別のアルゴリズムがあります。これは、格納されているいくつかの優先度を「破損」することが許可されている標準優先度キューのバリアントです。アルゴリズムについてはウィキペディアの記事で詳しく説明されていますが、基本的な考え方は、ソフトヒープを使用して、適切な分割が保証されているパーティション関数のピボットを効率的に（O（n）時間）選択することです。ある意味で、これは中央値の中央値アルゴリズムの修正バージョンであり、ピボット要素を選択するための（おそらく）より簡単なアプローチを使用します。

ソフトヒープは特に直感的ではありませんが、このペーパー（「チャゼルのソフトヒープのより簡単な実装と分析」）には、データ構造の場合の正式な説明と分析を含む、かなり良い説明があります。

ただし、非常に高速で最悪の場合のO（n）アルゴリズムが必要な場合は、イントロセレクトを調べることを検討してください。このアルゴリズムは実際には非常に優れています。まず、クイックセレクトアルゴリズムを使用します。このアルゴリズムは、ピボットをインテリジェントに選択し、それを使用してデータを分割します。これは実際には非常に高速ですが、最悪の場合の動作が悪くなります。イントロセレクトは、進行状況を追跡する内部カウンターを追跡することでこれを修正します。アルゴリズムがO（n 2）時間の経過とともに、アルゴリズムを切り替え、中央値の中央値などを使用して、最悪の場合の保証を保証します。具体的には、各ステップで破棄される配列の量を監視し、入力の半分が破棄される前に一定数のステップが発生した場合、アルゴリズムは中央値の中央値アルゴリズムに切り替わり、次のピボットが適切であることを確認します。次に、クイックセレクトを使用して再起動します。これにより、最悪の場合のO（n）時間が保証されます。

このアルゴリズムの利点は、ほとんどの入力で非常に高速ですが（クイックセレクトは非常に高速であるため）、最悪の場合の動作が非常に優れていることです。このアルゴリズムの説明は、関連する並べ替えアルゴリズムのイントロソートとともに、このペーパー（「イントロソートの並べ替えと選択アルゴリズム」）に記載されています。

お役に立てれば！

于 2011-09-09T18:34:47.670 に答える
3

コンテナにN百万個の要素がある場合は、実際にテストしてパフォーマンスを確認する必要があると思います。std::nth_elementこのアルゴリズムは、 O（n）が期待されることが保証されているように、STLライブラリ（C ++）にすでに実装されています。したがって、C ++を使用した場合は、いくつかのテストを簡単に実行して、目的のパフォーマンスが十分に優れているかどうかを確認できます。

注目すべき例外はC++です。これは、テンプレート化されたnth_elementメソッドに、予想される線形時間を保証します。

于 2011-09-09T08:27:24.567 に答える
1

場合によります。偶然に起こった最悪のケースを心配しているなら、私は気にしません。データが十分に大きくなると、最悪のケースが発生する可能性が低くなり、保護する価値がほとんどなくなります。

クライアントがサーバー上でサービス拒否を行うために最悪の場合の順序でデータを提供できる状況で選択を行う場合は、中央値の中央値を使用して最悪の場合の順序を保証する価値があります。パフォーマンスを大幅に損なうことはありません。

于 2011-09-09T08:38:20.737 に答える
0

更新しました：

クイックソートの発明者であるHoare自身が提案した、クイックソートの修正である線形時間アルゴリズムがあります。CLRSブックのセクション9.3「最悪の線形時間での選択」を参照することをお勧めします。random_partitionクイックソートのメソッド（パーティションにランダムピボットを使用）があると仮定した場合の簡単なアルゴリズムは次のとおりです。

FindKth(array, l, u, k)
{
   int m = random_partition(array, l, u);
   if m == k : return array[k] /*we have found the kth element*/
   if m > k: return FindKth(array, l, m-1, k); /* we have found element > kth largest, concentrate on the left partition */
   else: return FindKth(array, m+1, u, k-m); /* find the k-m th element in the right partition */
}

DonaldKnuthのTAOCPVol.3の並べ替えと検索p.633も参照できます。この方法の利点は、配列を完全に並べ替える必要がないことです。STL nth_permutationはこの手法を使用していると思います。メモのセクションを参照して、

于 2011-09-09T08:38:29.490 に答える