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

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

我对来回复制的开销感兴趣的原因是因为在典型的面试中，诸如给定一个前序遍历元素数组，转换为二叉搜索树之类的问题on，涉及数组.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 辩护说我将首先将 Array 转换为 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 到 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屋！