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复杂度

回答

相关问题