algorithm - k 個の最大要素を順番に見つける

Question

配列内の k 個の最大要素を順番に (つまり、最大要素から k 番目に大きい要素まで) 見つける最も速い方法は何ですか?

Answer 1

1 つのオプションは次のとおりです。

1. median-of-medians や introsort などの線形時間選択アルゴリズムを使用して、k 番目に大きい要素を見つけ、k 番目の要素以降のすべての要素が k 番目の要素よりも大きくなるように要素を再配置します。

2. ヒープソートやクイックソートなどの高速ソート アルゴリズムを使用して、k 番目からすべての要素をソートします。

ステップ (1) には O(n) の時間がかかり、ステップ (2) には O(k log k) の時間がかかります。全体として、アルゴリズムは時間 O(n + k log k) で実行され、非常に高速です。

お役に立てれば！

Answer 2

基数ソートのソリューション:

• 基数ソートを使用して、配列を降順にソートします。
• 最初の K 要素を出力します。

時間計算量: O(N*L) (L = 最大要素の長さ) は、L = O(1) と仮定できます。使用されるスペース: 基数ソートの O(N)。

ただし、基数ソートにはコストのかかるオーバーヘッドがあり、線形時間の複雑さが魅力的ではないと思います。

Answer 3

C++ はまた、O(n log k) の時間計算量で最小の k 個の要素 (並べ替えられた) を選択する問題を解決する partial_sort アルゴリズムを提供します。最大の k 個の要素を選択するためのアルゴリズムは提供されていません。これは、順序付け述語を反転することによって行う必要があるためです。

Perl の場合、CPAN から入手できるモジュール Sort::Key::Top は、いくつかの順序付けとカスタム キー抽出手順を使用して、リストから上位 n 要素を選択する一連の関数を提供します。さらに、Statistics::CaseResampling モジュールは、quickselect を使用して分位数を計算する関数を提供します。

Python の標準ライブラリ (2.4 以降) には heapq.nsmallest() と nlargest() が含まれており、ソートされたリストを返します。前者は O(n + k log n) 時間、後者は O(n log k) 時間です。

Answer 4

@templatetypedef のソリューションは、入力を変更またはコピーできると仮定すると、おそらく最速のソリューションです。

または、ヒープまたは BST ( setC++ の場合) を使用して、特定の時点で最大の k 個の要素を格納し、配列の要素を 1 つずつ読み取ることができます。これは O(n lg k) ですが、入力を変更せず、O(k) の追加メモリのみを使用します。ストリームでも機能します (最初からすべてのデータを把握していない場合)。