セット内の最大のX番号をソートする最良のアルゴリズムは何ですか

Question

N個の数字の集合（N> X）からX個の最大の数字のソートされたリストを抽出する最良のアルゴリズムは何ですか？ほとんどのアルゴリズムでは、O(NlogN)時にそれを行うことができます。しかし、それ以上のことは可能でしょうか？たとえば、バイナリツリーの場合：O(NLogX)？セット内の数字は完全にランダムです。

Answer 1

使用サイズX.

挿入ヒープに最初X要素のmin heap。要素X +1（eと呼びます）から、これをヒープの先頭と比較してm（これまでの最小値）と比較してください。この比較は一定の時間内に行われることに注意してください。 もしE>メートル、次いでEは（メートルを抽出し、Eを挿入）で取得するに値します。セットの各要素に対してそれを行います。このプロセスが終了すると、ヒープにはXという大きな数値が含まれています。その後、抽出 - 最小X回あなたが期待する並べ替えられたリストを提供します。最初のステップは、O(NlgX)時間であるよう

N反復の各々は、電位O(lgX)抽出/挿入操作を行います。最小ヒープでのXの抽出 - 最小のコストは、単にO(XlgX)となり、全体の複雑さはO(NlgX)になります。

Answer 2

"ベスト"アルゴリズムは、データセットのサイズ、元のリストを変更できるかどうか、および選択するアイテムの数など、多くの要素によって異なります。

たとえば、10個のアイテムがあり、最大の3個を探している場合は、リストを並べ替えて最後の3個を選ぶだけです。 Quickselectに電話して、配列の順序を変更して、3つの最大値が前面になるように並べ替え、次にそれらの3つを並べ替えることがあります。しかし、保存する時間が少ないので、複雑さを増やす価値はありません。

10,000からトップ1000を選びたい場合は、間違いなくQuickselectを使用します。 QuickselectはO（n）ですが、QuicksortはO（n log n）です。 QuicksortとQuickselectの両方が元のリストを変更します。

元のリストを変更できない場合、またはリスト全体をメモリに保持できない場合は、前の回答に記載されているヒープ選択アルゴリズムが最適な方法です。

また、QuickselectがO（n）であり、ヒープ選択アルゴリズムがO（n log x）であっても、ヒープ選択アルゴリズムはQuickselectよりも高速です。 。たとえば、1,000,000の中から上位100を選択する場合は、ヒープ選択アルゴリズムが高速になります。私はこのブログについてかなり詳細な記事を書きました。 When theory meets practiceを参照してください。

Answer 3

Xが小さい場合は、挿入の並べ替えが有効です。

ビデオゲームの「トップ10スコア」リストを考えてください。ゲームをプレイした後、リストはどうなりますか？あなたのスコアが10位のスコアより高い場合を除いて、何も起こらない：あなたのスコアはリストを作るには低すぎる。しかし、あなたのスコアがリストを作成するのに十分高い場合、挿入ソートはリストの適切な場所にそれを置き、下のすべてのスコアをそこから外して余裕を持たせます。この後者の場合、古い10位のスコアは新しい11位のスコアになり、リストから外れます。