将列表复制回数组的时间复杂度是多少,反之亦然？

Question

我想知道什么是时间复杂的大O(n)符号]的 ArrayList到Array转换:

ArrayList assetTradingList = new ArrayList();
assetTradingList.add("Stocks trading");
assetTradingList.add("futures and option trading");
assetTradingList.add("electronic trading");
assetTradingList.add("forex trading");
assetTradingList.add("gold trading");
assetTradingList.add("fixed income bond trading");
String [] assetTradingArray = new String[assetTradingList.size()];
assetTradingArray.toArray(assetTradingArray);

类似地,数组以下列方式列出的时间复杂度是多少:

方法1使用Arrays.asList:

String[] asset = {"equity", "stocks", "gold", "foreign exchange","fixed
    income", "futures", "options"};
List assetList = Arrays.asList(asset);

方法2使用collections.addAll:

    List assetList = new ArrayList();
    String[] asset = {"equity", "stocks", "gold", "foreign exchange", "fixed
        income", "futures", "options"};
    Collections.addAll(assetList, asset);

方法3 addAll:

     ArrayList newAssetList = new ArrayList();
     newAssetList.addAll(Arrays.asList(asset));

我对来回复制的开销感兴趣的原因是因为在典型的访谈中,问题来自诸如此类given an array of pre-order traversal elements, convert to binary search tree,涉及到arrays.与List提供一大堆诸如操作remove等,这将使其简单的使用代码List比Array.

在这种情况下,我想保护我使用列表list数组`说"我会先将数组转换为List,因为这个操作的开销并不多(希望如此)".

建议用于来回复制元素的任何更好的方法arrays都会更快.

谢谢

Answer 1

这似乎Arrays.asList(T[]);是最快的O(1)

因为该方法返回不可修改的List,所以没有理由将引用复制到新的数据结构.该方法仅使用给定数组作为List它返回的不可修改实现的后备数组.

其他方法似乎是将每个元素逐个复制到底层数据结构.ArrayList#toArray(..)使用System.arraycopy(..)内心深处(O(n)但更快,因为它本地完成).Collections.addAll(..)循环遍历数组元素(O(n)).

使用时要小心ArrayList.当达到其容量时,背衬阵列的尺寸加倍,即.当它满了.这需要O(n)时间.ArrayList除非您知道从一开始就添加了多少元素并使用该大小创建它,否则添加到一个可能不是最好的想法.

Answer 2

由于 的支持数据结构ArrayList是一个数组，并且数组元素的复制是 O(n)，所以它是 O(n)。

我看到的唯一开销是这些中间对象对堆的污染。大多数时候，开发人员（尤其是初学者）并不关心这一点，而是将 Java GC 视为一根魔杖，可以清理它们之后的所有内容。我个人的观点是，如果您可以避免不必要的数组到列表的转换，反之亦然，那就这样做。

如果您事先知道列表的可预见（例如定义的）大小，请使用构造函数预先分配其大小，以避免在容量耗尽时ArrayList(int size)在内部发生内部数组复制。ArrayList根据用例，考虑其他实现，例如LinkedList，如果您只对随后添加到列表和迭代读取感兴趣。