[解決済み】10億個の数字の配列から最大100個の数字を求めるプログラムを作成せよ

質問

先日、面接で「10億個の数字の配列から最大100個の数字を求めるプログラムを作成せよ」と問われました。

私は、時間計算量O(nlogn)で配列をソートし、最後の100個の数字を取り出すというブルートフォース・ソリューションしか与えることができなかった。

Arrays.sort(array);

面接官はより良い時間複雑性を求めていました。私は他の解決策をいくつか試しましたが、彼に答えることはできませんでした。より良い時間複雑性の解決策はありますか？

どのように解決するのですか？

100個の大きな数字の優先キューを用意しておき、10億個の数字を繰り返し処理し、キュー内の最小の数字（キューの先頭）より大きな数字に出会うたびに、キューの先頭を削除し、新しい数字をキューに追加すればよいのです。

EDIT Devが指摘したように、ヒープで実装された優先キューでは、キューへの挿入の複雑さは O(log N)

最悪の場合、次のようになります。 billion*log2(100) よりも優れています。 billion*log2(billion)

一般に、N個の数の集合から最大のK個の数が必要な場合、その複雑さは O(N log K) よりも O(N log N) これは、KがNに比べて非常に小さい場合、非常に大きな意味を持つことがあります。

EDIT2です。

このアルゴリズムの期待時間は、各反復で挿入が起こるかもしれないし起こらないかもしれないので、かなり興味深いです。i 番目の番号がキューに挿入される確率は、ランダム変数が少なくとも i-K 同じ分布からの確率変数（最初のk個の数値は自動的にキューに加えられる）。順序統計学を利用することができます ( リンク ) を使って、この確率を計算することができます。例えば、次の数字から一様にランダムに選んだとします。 {0, 1} とすると、（i-K）番目の番号（i個の番号のうち）の期待値は (i-k)/i であり、確率変数がこの値より大きくなる確率は 1-[(i-k)/i] = k/i .

したがって、挿入の期待回数は

そして、予想される実行時間は次のように表すことができる。

( k でキューを生成する時間です。 k 要素、次に n-k の比較と、上記のような挿入の予想数から、それぞれ平均的な log(k)/2 時間)

ただし N と比較して非常に大きい K この式は n よりも、むしろ N log K . これは、質問の場合、1万回（10億回と比較すると非常に小さい）繰り返した後でも、キューに挿入される数字の確率が非常に小さいので、多少直感的に理解できます。