java ArrayList对象构造函数是如何工作的,它们的时间复杂度是多少?
我试图收集有关ArrayList类中的构造函数如何工作的信息,以及类项目的时间复杂性
在https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList()的API文档中
它指出get()、set()isEmpty()、iterator()和listIterator()是唯一的O(1)方法
我认为这意味着构造器是O(n),但我似乎找不到任何明确说明这一点的东西,也找不到构造器是如何工作的
如有任何见解,将不胜感激
# 1 楼答案
ArrayList(int)
基本上只分配一个大小为n的数组,其他什么都不分配。这在技术上可能是O(n),但分配的复杂性是。。。它本身相当复杂,而且通常只有O(1),尽管之后在垃圾收集器中会有开销ArrayList(Collection)
基本上只需调用目标集合上的toArray()
并使用它,这将需要。。。不管集合类型需要多长时间,它基本上总是O(n)