ArrayList對象 - 構造函數是如何工作的，它們的時間複雜度是多少？

Question

我想收集有關ArrayList類中的構造函數如何工作以及它們的時間複雜度是什麼的類項目的信息。

。在https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList() API文檔，

它指出的get（），（）設置的isEmpty（），迭代器（），和的ListIterator（）是唯一的O（1）方法。

我想這意味着構造函數是O（n），但我似乎無法找到任何具體說明這一點，也沒有如何構造函數。

任何有識之士將不勝感激。

Answer 1

ArrayList(int)基本上只是分配一個大小爲n的數組，而沒有別的。這可能在技術上是O（n），但分配的複雜性本身相當複雜，並且經常只是O（1）儘管在垃圾收集器中有開銷...

ArrayList(Collection)基本上只會調用toArray()目標集合和使用，這將採取......無論這種集合類型，這基本上總是O（n）需要很長時間。