0

配列の長さが n で、1 <= m <= n^0.5 の場合

選択アルゴリズムを使用して、m 番目に小さい整数 ( http://en.wikipedia.org/wiki/Selection_algorithmに O(n) であるBFPRT と呼ばれる複雑なものがあります) を見つけて、それをピボットとして使用できると思います。配列を分割して、最初の m 個の最小整数を取得します。

しかし、最小ヒープなどのデータ構造を使用してこれを行う方法はありますか? そして、それがO(n)かどうかをどうやって知ることができますか?

4

3 に答える 3

4

線形時間で最小ヒープを作成できます。次に、各削除の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))

于 2013-04-16T07:53:24.203 に答える
0

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)

于 2013-04-21T02:50:05.753 に答える