java - コレクションから PriorityQueue を構築する時間の複雑さはどれくらいですか?

Question

を使用した Java の PriorityQueue コンストラクターの複雑さは何Collectionですか? 私はコンストラクタを使用しました：

PriorityQueue(Collection<? extends E> c)

複雑さは O(n) または O(n*log(n)) ですか?

Answer 1

コレクションからを初期化する時間の複雑さPriorityQueueは、ソートされていないものであっても O(n) です。内部的には、これはsiftDown()配列をインプレースで「ヒープ化」するために呼び出されるプロシージャを使用します。(これは文献ではプッシュダウンとも呼ばれます。)

これは直感に反します。要素をヒープに挿入すると O(log n) のように見えるため、n 個の要素を挿入すると O(n log n) の複雑さが生じます。これは、要素を 1 つずつ挿入する場合に当てはまります。(内部的には、個々の要素を挿入すると、 を使用してこれが行われsiftUp()ます。)

個々の要素をヒープ化するのは確かに O(log n) ですが、その「トリック」siftDown()は、各要素が処理されるにつれて、ふるいにかける必要のある要素の数が継続的に減少することです。したがって、複雑さの合計は n 要素 x log(n) ではありません。これは、残りの要素をふるいにかけるコストの減少の n 項の合計です。

この回答を参照してください。また、数学を通じて機能するこの記事も参照してください。