java - 在 Java 中将列表复制回数组的时间复杂度是多少，反之亦然？

Question

我想知道时间复杂度是多少 [in big 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 辩护而不是 arrays说“我会先将 Array 转换为 List，因为此操作的开销不大(希望如此)”。

推荐用于从 array to list 来回复制元素的任何更好的方法那会更快也很好知道。

谢谢

Answer 1

看起来 Arrays.asList(T[]); 是最快的 O(1)

因为该方法返回一个不可修改的 List，所以没有理由将引用复制到新的数据结构。该方法只是将给定数组用作其返回的不可修改的 List 实现的后备数组。

其他方法似乎将每个元素一个一个地复制到底层数据结构中。 ArrayList#toArray(..) 使用 System.arraycopy(..) 深入(O(n) 但速度更快，因为它是 native 完成的) . Collections.addAll(..) 遍历数组元素 (O(n))。

---

使用 ArrayList 时要小心。当达到其容量时，后备阵列的大小加倍，即。当它满了。这需要 O(n) 时间。添加到 ArrayList 可能不是最好的主意，除非您从一开始就知道要添加多少元素并使用该大小创建它。