java ArrayList对象构造函数是如何工作的，它们的时间复杂度是多少？

Question

我试图收集有关ArrayList类中的构造函数如何工作的信息，以及类项目的时间复杂性

在https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList()的API文档中

它指出get（）、set（）isEmpty（）、iterator（）和listIterator（）是唯一的O（1）方法

我认为这意味着构造器是O（n），但我似乎找不到任何明确说明这一点的东西，也找不到构造器是如何工作的

如有任何见解，将不胜感激

Answer 1

ArrayList(int)基本上只分配一个大小为n的数组，其他什么都不分配。这在技术上可能是O（n），但分配的复杂性是。。。它本身相当复杂，而且通常只有O（1），尽管之后在垃圾收集器中会有开销

ArrayList(Collection)基本上只需调用目标集合上的toArray()并使用它，这将需要。。。不管集合类型需要多长时间，它基本上总是O（n）