在 Java 中将列表复制回数组以及反之亦然的时间复杂度是多少? [英] what is the time complexity for copying list back to arrays and vice-versa in Java?

问题描述

我想知道 ArrayList 到 Array 转换的时间复杂度 [以大 O(n) 表示法] 是多少:

I am wondering what is the time complexity [in big O(n) notations] of ArrayList to Array conversion:

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);

同样，数组以下列方式列出的时间复杂度是多少:

similarly, what is the time complexity for arrays to list in the following ways:

使用Arrays.asList的方法1:

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

使用collections.addAll的方法2:

    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));

我之所以对来回复制的开销感兴趣是因为在典型的面试中，问题会出现，例如给定一个前序遍历元素数组，转换为二叉搜索树等等上，涉及数组.List 提供了一大堆操作，例如 remove 等，使用 List 比使用 Array.

The reason I am interested in the overhead of copying back and forth is because in typical interviews, questions come such as given an array of pre-order traversal elements, convert to binary search tree and so on, involving arrays. With List offering a whole bunch of operations such as remove etc, it would make it simple to code using List than Array.

在这种情况下，我想为我使用 list 而不是 arrays 辩护说我会首先将数组转换为列表，因为此操作的开销是不多(希望如此)".

In which case, I would like to defend me for using list instead of arrays saying "I would first convert the Array to List because the overhead of this operation is not much (hopefully)".

推荐用于从 array 到 list 来回复制元素的任何更好的方法会更快，这也是很好知道的.

Any better methods recommended for copying the elements back and forth from array to list that would be faster would be good know too.

谢谢

推荐答案

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

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

Because the method returns an unmodifiable List, there is no reason to copy the references over to a new data structure. The method simply uses the given array as a backing array for the unmodifiable List implementation that it returns.

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

The other methods seem like they copy each element, one by one to an underlying data structure. ArrayList#toArray(..) uses System.arraycopy(..) deep down (O(n) but faster because it's done natively). Collections.addAll(..) loops through the array elements (O(n)).

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

Careful when using ArrayList. The backing array doubles in size when its capacity is reached, ie. when it's full. This takes O(n) time. Adding to an ArrayList might not be the best idea unless you know how many elements you are adding from the beginning and create it with that size.

这篇关于在 Java 中将列表复制回数组以及反之亦然的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！