0

k入力配列から最上位の要素を返す効率的な方法を探しています。1 つの方法は、配列をソートし、配列の末尾から要素
を返すことです。k

hereで提案されている他の方法があり、そのうちの 1 つはquickselect アルゴリズムを使用しますが、私の理解では、quickselect はkソートされていない配列の 番目の要素のみを返します。戻った後、左右の要素kはまだソートされていません。

したがって、次のようになります。

while k>0{
   quickselect(int[] arr, k);
   k--;
}

クイック選択はO(n)であり、それを2k回行うので、全体的な時間の複雑さはO(n*k)です。
しかし、投稿のデータは、これが よりも優れていることを示唆していますO(n log n)。
100 万のサンプルから上位 200 を選択すること200 millionは、前者の場合を意味しますが20 million、後者の場合を意味します。明らかに、これははるかに優れています。

上位 200 個の要素を選択するために quickselect を使用する方法を理解していますか?

4

2 に答える 2

4

いいえ、時間は必要ありませんO(nk)- O(n)(平均的なケース) で実行できます。

クイック選択の最終結果は、配列の末尾から k 番目の位置にある k 番目の要素であり、小さい要素が左側に、大きい要素が右側に配置されます。

したがって、その要素から右側のすべての要素は k 個の最大要素になります。これらをO(k)(単純な for ループで) 抽出するのは簡単で、合計実行時間はO(n).

または、quickselect を実行した後に k 番目の要素がわかるので、配列をもう一度調べて、その要素より大きいか等しいすべての要素を抽出することもできます (これは 1 回のパスで行うこともできますO(n))。

O(k log k)ソートされた順序でそれらを返したい場合は、(それらをソートするために)追加が必要になります。

于 2014-02-20T00:20:02.327 に答える