Java Collection addAll複雜度

是否存在複雜度爲O（1）而不是用於addAll操作的O（n）的Java集合，還是必須實現自己的集合？使用高效的鏈接列表，Collection1.addAll（Collection2）操作應該將第二個集合附加到第一個將collection2的第一個節點添加到集合1的最後一個節點，其他節點遵循。但這並不是說我讀到了似乎使用Iterator的文檔，所以我想複雜度是O（collection2.size）。Java Collection addAll複雜度

是嗎？

來源

2016-07-12 Kaizokun

http://stackoverflow.com/questions/6540511/time-complexity-for-java-arraylist –

可能[This SO Post]（http://stackoverflow.com/questions/559839/big-o-summary -for-java-collections-framework-implementation）可以幫助你。 – Sanjeev

感謝您的鏈接 – Kaizokun

即使鏈接列表的優化只有在將項目從一個鏈接列表移動到另一個時纔可用。

然而，你可以建立一個自己的集合，它有一個更多的間接層次，即其中包含一系列集合。這樣，添加整個集合是很便宜的，迭代也是如此。然而，索引或長度確定可能變得非常昂貴。

來源

2016-07-12 09:04:37 glglgl

謝謝，當然這是真的取決於案件。對於長度的確定，只需添加兩種尺寸即可完成我認爲的工作。 – Kaizokun

@Kaizokun如果只有兩個。如果你設計這個類具有最大的靈活性，也許它會更多。 – glglgl

當然每次我追加一個集合我加起來的大小:) – Kaizokun

ArrayList可能和它在這方面一樣好，但它實際上也取決於提供的集合。最好的情況下複雜度是O（1），但只有當提供的Collection的toArray()方法也具有恆定的複雜度時纔是如此。

的System.arrayCopy（）調用，它實際分配~~是O（1），反正~~是複雜的，見下圖：

// 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一些分歧是一個固定時間操作。 Some say no。 Others suggest it is。

根據to this benchmark I hacked together，它位於中間的某處。複製時間保持幾乎不變，最多約100個數組項目，但從這裏開始線性增長，我猜測某種分頁涉及到那裏。有效地，System.arrayCopy具有線性時間複雜度，除非陣列非常小。

來源

2016-07-12 09:10:53

謝謝你，在我的情況下集合是一個鏈表（鏈表我不知道如何說英語）所以toArray操作是O（n）我猜。 – Kaizokun

你確定嗎？ http://stackoverflow.com/questions/7165594/time-complexity-of-system-arraycopy聲稱不同。此外，我很確定'ensureCapacityInternal'也在'O（N）'中。 – fabian

第一部分是宗教戰爭的來源，屬實。我認爲從Java的角度來看，這是一個原子操作。這裏有分歧，但這個答案支持我的理論：http://stackoverflow.com/a/2772176/342852 –

Java Collection addAll複雜度

回答

相關問題