k個の最大要素を抽出する

Question

整数がn個ある場合、O（k + logn）時間でn個の値からk個の最大要素をリストすることは可能ですか？私が得た最も近いのは、最大ヒープを構築し、最大k回抽出することです。これにはO（klogn）時間がかかります。また、インオーダートラバーサルの使用についても考えます。

Answer 1

は、あなたはそれがのアイデアクイックソートを使用しているので、時にはクイック選択と呼ばれているarray.Techniqueからk番目の要素を抽出するための分割統治技術を使用することができます。

クイックソートは、我々は、その正確な位置とその周囲partitionアレイにピボット要素を移動する、pivot要素を選びます。アイデアは、は完全なクイックソートをしないが、ピボット自体がk番目に小さい要素であるところで停止する。また、ピボットの左右両側を再発するのではなく、ピボットの位置に従って一方を再発させます。この方法の最悪の場合の時間複雑度はO(n^2)ですが、平均でO(n)で動作します。

Answer 2

ヒープの構築にはO（nlogn）が必要であり、k個の要素の抽出にはO（klogn）が必要です。 k要素の抽出がO（klogn）であるという結論に達した場合は、ヒープを構築するのにかかる時間が心配されていないことを意味します。

その場合、リスト（O（nlogn））をソートし、k個の最大要素（O（k））を取ります。

Answer 3

この問題を解決する方法。

1. データをソートし、トップkを取る。ソートにはO(n lg n)が必要で、先頭kを反復するにはO(k)が必要です。合計時間：O(n lg n + k)

2. データから最大ヒープを作成し、上位k回を削除します。ヒープの構築はO(n)で、トップアイテムを削除する操作はO(lg N)です。合計時間：O(n) + O(k lg n)

3. 最大サイズkの実行中の最小ヒープを維持します。すべてのデータを繰り返し、ヒープに追加してから、ヒープ全体を取得します。合計時間：O(n lg k) + O(k)

4. k番目に大きい値を見つけるために選択アルゴリズムを使用します。次に、すべてのデータを繰り返して、その値より大きいすべての項目を検索します。

   a。平均実行時間がO(n)であるが、最悪の場合はO(n^2)であるQuickSelectを使用してk番目に大きいものを見つけることができます。合計平均ケースタイム：O(n) + O(n) = O(n)最悪の場合の合計時間：O(n^2) + O(n) = O(n^2)

   b。最悪の場合の実行時間がO(n)であるが、インプレースではないmedian-of-mediansアルゴリズムを使用して、k番目に大きいものを見つけることもできます。合計時間：O(n) + O(n) = O(n)