c# - C#: N x N 行列で最大の m 要素を見つける効率的なアルゴリズム

Question

次のようなメソッドヘッダーを使用して、N x N マトリックスで最大の m 個の要素を見つける効率的なアルゴリズムがあるかどうかを知りたいです。

double[] greatestValues(double[][] matrix, int numberOfElements);

何か案は？

Answer 1

N x N 行列を N x N 項目の配列として扱う場合は、次の手法のいずれかを適用できます。

クイック ソート ベースの選択アルゴリズムの直接適用クイック ソート ベースの選択アルゴリズムを使用して、最小の k 個の要素または最大の k 個の要素を見つけることができます。k 個の最小要素を見つけるには、中央値の中央値クイック ソート ベースのアルゴリズムを使用して、k 番目に最小の要素を見つけます。k 番目に小さい要素を見つける分割の後、k 番目に小さい要素よりも小さいすべての要素は k 番目の要素の左側に存在し、それより大きいすべての要素は k 番目に小さい要素の右側に存在します。したがって、1 番目から k 番目の要素までのすべての要素が、k 個の最小要素を構成します。時間計算量は、要素の総数 n に対して線形です。

データ構造ベースのソリューションもう 1 つの簡単な方法は、リストの各要素を順序付けられたセット データ構造 (ヒープや自己平衡二分探索木など) に追加することです。要素は最大 k 個です。データ構造に k 個を超える要素がある場合は常に、O(log k) 時間で実行できる最大の要素を削除します。各挿入操作にも O(log k) 時間がかかるため、全体で O(nlog k) 時間になります。

リストを Θ(n) 時間でヒープに変換し、要素を優先度キューに配置する修正された幅優先検索アルゴリズムを使用してヒープをトラバースすることができます (通常、 BFS)、正確に k 個の要素をトラバースした後にスキャンを終了します。トラバーサル全体でキュー サイズが O(k) のままであるため、完了までに O(klog k) の時間が必要になり、このアルゴリズムでは O(n + klog k) の時間制限が発生します。

ここから。