在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:

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

我对来回复制的开销感兴趣的原因是，在典型的采访中，诸如给出了一系列预遍历元素，转换为二进制搜索树之类的问题等，涉及到 arrays .借助 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 辩护说:我首先将数组转换为List，因为此操作的开销是(希望如此)".

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到列表来回复制，这样会更快.

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

谢谢

推荐答案

在 O(1)看来， Arrays.asList(T []); 最快.代码>

由于该方法返回了不可修改的 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屋！