JavaコレクションaddAllの複雑さ

Question

複雑なO（1）のJavaコレクションがありますが、addAll操作ではO（n）ではありませんか、独自のコレクションを実装する必要がありますか？効率的なリンクされたリストでは、Collection1.addAll（Collection2）操作は、コレクション2の最初のノードをコレクション1の最後に追加する最初のコレクションに2番目のコレクションを追加する必要があります。しかし、Iteratorを使用していると思われるドキュメントを読んでいるわけではないので、複雑さはO（collection2.size）だと思います。

そうですか？

Answer 1

リンクリストの最適化さえ、のリンクリストから別のリンクリストにアイテムを移動した場合にのみ機能します。

ただし、1つ以上のレベルの間接化を持つコレクションを作成することはできます。 e。これにはコレクションのコレクションが含まれています。この方法では、コレクション全体を追加することはかなり安価であり、繰り返されます。しかし、索引付けや長さの決定は非常に高価になります。

Answer 2

ArrayListはおそらくこの点では優れていますが、実際には付属のコレクションにも依存します。最良の場合の複雑さはO（1）ですが、提供されたCollectionのtoArray()メソッドも一定の複雑さを持つ場合のみです。

// java.util.ArrayList.addAll 
// Oracle JDK 1.8.0_91 
public boolean addAll(Collection<? extends E> c) { 
    Object[] a = c.toArray(); // O(?) <-- depending on other type 
    int numNew = a.length; 
    ensureCapacityInternal(size + numNew); // Increments modCount 
    System.arraycopy(a, 0, elementData, size, numNew); 
    size += numNew; 
    return numNew != 0; 
} 

をSystem.arrayCopyは、一定時間操作であるか否かにいくつかの意見の相違があります：実際に割り当てを行い

System.arraycopyの（）の呼び出しはO（1）、とにかくは下記を参照してください、複雑です。 Some say no。 Others suggest it is。

to this benchmark I hacked togetherによれば、真ん中にあります。コピータイムは約100の配列アイテムまでほぼ一定ですが、そこから線形に成長し、私はいくつかの種類のページングがそこに関わっていると推測しています。したがって、配列が非常に小さい場合を除き、System.arrayCopyは線形時間の複雑さを持ちます。