PriorityQueueのaddAllメソッドの複雑さは何ですか。一度に1つの要素を追加してO（n log n）にしますか、それともO（n）時間で順序付けられていない要素からヒープを作成するビルドヒーププロセスを使用しますか？
質問する
5105 次
3 に答える
8
Javadocは、それが一連の追加として実装されるAbstractQueueaddAllから継承されていることを示唆しているようです。
これにより、複雑さはO(mlogn)、mが挿入されるコレクションのサイズであると私は信じるようになります。
于 2013-01-14T01:15:44.050 に答える
3
優先キューから
...この実装は、エンキューおよびデキューメソッドにO（log（n））時間を提供します...
したがって、仮定することしかできませんn log(n)。
しかし-明らかに-これはあなたが想定できることだけです。使用する予定の特定の実装によっては、問題を改善できるいくつかのトリックが見つかる場合があります。
于 2013-01-14T01:17:34.897 に答える
2
OpenJDKを見ると、PriorityQueueはAbstractQueueからaddAll実装を継承しているように見えます。この実装は、コレクションを反復処理し、各要素でaddを呼び出します。
于 2013-01-14T01:16:12.323 に答える