「トーナメント」アルゴリズムを使用して、サイズの配列で2番目に大きい要素を見つけることができることを知っています。同様の「トーナメント」を使用して、 k 番目に大きい要素を見つけることができるかどうか疑問に思います。NN+log(N)-2
k 番目に大きい要素O(N)を見つけるための「選択」アルゴリズムがあることは知っています。にある「良い」ピボットで使用します。の配列からa を構築し、からk要素を取得することもできます。Quick SelectO(N)heapO(N)heap
別のアプローチがあるのだろうか。
これを O( N log k ) アルゴリズムにすることができると思います: 配列を反復処理し、これまでに遭遇した最大のk要素の最小ヒープを維持します。したがって、最初のk 個の要素は直接ヒープに入ります。後続のすべての要素はヒープの先端と比較され、それが大きい場合は先端がヒープから削除され、新しい要素が挿入されます。これは、サイズkのヒープに対する O(log k ) 操作です。アルゴリズムが完了し、シーケンスの長さが少なくともkである場合、ヒープの先端にはk番目に大きな要素があり、残りのヒープにはそれより大きい要素があります。
このアプローチは、中央値の中央値 O( n ) ソリューションよりも最悪の場合の動作が劣りますが、実装がはるかに簡単で、小さなkに対してかなり良好な動作が得られます。したがって、多くの実用的なアプリケーションに適している可能性があります。