配列の長さが n で、1 <= m <= n^0.5 の場合
選択アルゴリズムを使用して、m 番目に小さい整数 ( http://en.wikipedia.org/wiki/Selection_algorithmに O(n) であるBFPRT と呼ばれる複雑なものがあります) を見つけて、それをピボットとして使用できると思います。配列を分割して、最初の m 個の最小整数を取得します。
しかし、最小ヒープなどのデータ構造を使用してこれを行う方法はありますか? そして、それがO(n)かどうかをどうやって知ることができますか?
線形時間で最小ヒープを作成できます。次に、各削除のmコストで最小要素時間を削除するだけです。log(n)それO(n) + m*O(log(n))はどれがO(n) + O(sqrt(n)*log(n))どれですO(n)。
編集私が最初に言ったのO(n) + O(sqrt(n)*log(n))はO(sqrt(n)*log(n))どちらが間違っているかということですO(n)。o(sqrt(n)*log(n))O(sqrt(n)*log(n))
Build_Heap(A) method can create min_heap or max_heap from random array in O(n) time , if we creates min_heap then it takes O(1) time to get smallest element
so total time to get smallest element is O(n)+)(1) that is O(n)