5

n個のdouble値を含むリストがあり、そのリストでk個の最小のdouble値を見つける必要があります

  • kはnよりはるかに小さい
  • n個のdouble値を持つ初期リストはランダムに並べられています
  • 見つかったk個の最小のdouble値をソートする必要はありません

どのアルゴリズムをお勧めしますか？

現時点では、クイックソートを使用してリスト全体を並べ替えてから、並べ替えられたリストから最初のk個の要素を取り出します。もっと速いアルゴリズムがあるはずだと思います。

ご協力ありがとうございました！！！

4

5 に答える 5

10

Pythonの標準ライブラリのnlargest（）コードに一致するようにソリューションをモデル化できます。

  • maxheapの最初のk値をヒープ化します。
  • 残りのn-k値を繰り返し処理します。
  • それぞれをヒープの上部の要素と比較します。
  • 新しい値が低い場合は、ヒープ事前配置操作を実行します（これにより、最上位のヒープ要素が新しい値に置き換えられ、それが下にシフトされます）。

アルゴリズムは驚くほど効率的です。たとえば、n=100,000およびk=100の場合、ランダムに配置された入力の比較回数は通常約106,000です。これは、単一の最小値を見つけるための100,000をわずかに超える比較です。また、データセット全体の完全なクイックソートよりも約20分の1の比較しか行いません。

さまざまなアルゴリズムの相対的な強さは、http： //code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallestで調査および要約されています。

于 2012-07-10T05:55:44.153 に答える
8

選択アルゴリズムを使用して、k番目に低い要素を見つけ、それとそれより低いすべての要素を繰り返して返すことができます。リストに重複が含まれている可能性がある場合は、さらに作業を行う必要があります（必要な要素が増えないようにしてください）。
この解決策はO(n)です。選択アルゴリズムは、C++で次のように実装されます。nth_element()

もう1つの方法は、サイズの最大ヒープkを使用し、ヒープを維持しながら要素を反復して、k個の最小要素すべてを保持することです。

for each element x:
   if (heap.size() < k):
      heap.add(x)
   else if x < heap.max():
      heap.pop()
      heap.add(x)

完了すると、ヒープにはk個の最小要素が含まれます。
このソリューションはO(nlogk)

于 2012-07-10T05:30:01.723 に答える
2

C++標準ライブラリのpartial_sortアルゴリズムを見てください。

于 2012-07-10T05:31:16.143 に答える
2

std::nth_elementを使用できます。これはO（N）の複雑さです。これは、要素を並べ替えず、特定のNの下にあるすべての要素がNより小さくなるように要素を配置するだけだからです。

于 2012-07-10T05:32:05.427 に答える
0

選択ソートを使用できます。最初の最小値を選択するにはO（n）が必要です。位置1にこの最小値を設定したら、データセットを再スキャンして、2番目に低い値を見つけることができます。k番目に低い値になるまでそれを行うことができます。このように、kがnよりも十分に小さい場合、O（n）と同等の複雑さknが得られます。

于 2012-07-10T11:35:35.690 に答える