Arraylist 时间复杂度：您是否同时根据需要复制和移动元素？

Question

我想弄清楚这两种方法在时间复杂度上的区别：

public ArrayList<Integer> populateList(int n){
  ArrayList<Integer> list = new ArrayList<Integer>();
  for(int i=0; i< n; i++)
     list.add(0, i);
     return list;
  }

public ArrayList<Integer> populateList(int n){
  ArrayList<Integer> list = new ArrayList<Integer>();
  for(int i=0; i< n; i++)
    list.add(i);
    return list;
  }

我知道 big-o 是根据最坏情况定义的，添加到 arraylist 的最坏情况涉及调整大小，从而将所有元素复制到新数组中。我认为方法 2 是 O(n^2) 因为对于数组中的每个元素，您可能必须将所有元素复制到一个更大的数组中。

但是我不确定方法1，因为我不确定事情的完成顺序。似乎可以将复制元素和插入新元素结合起来，这样您就不必先将旧元素添加到更大的列表中，然后在添加新元素时根据需要移动所有元素。如果是这样的话，方法 1 似乎是 O(n^2) 而不是 O(n^3)。但这是怎么回事？

Answer 1

方法一是O(n^2)

方法2比O(n^2)好很多：存储数据的内部数组分配了一些空闲space，内部数组增长是指数级的，所以n个元素的迭代只发生很少。由于您在末尾追加，因此没有其他理由在每一步迭代所有元素。

Answer 2

ArrayList 由数组支持。如果 "insert" 数组头部的一个元素，则必须将所有其他元素向右移动一个以腾出空间。这意味着单次调用：

list.add(0, i);

是O(n)，因为每个元素（已经添加）都必须移动。
如果你这样做 n 次，就是 O(n^2).

但是在（后备）数组的末尾添加一个元素：

list.add(i);

只需要在数组的一个未使用的元素中放一个值，即O(1)，除非数组已满，需要分配和复制另一个更大的数组，即O(n) ，但这只会随着数组的增长而不断降低的频率发生，特别是 O(log n).

如果你做的操作是O(1)，除了O(n)每log n次，n次，那就是O(n log n).

Arraylist 时间复杂度：您是否同时根据需要复制和移动元素？

Arraylist time complexity: do you copy over and shift elements as needed at the same time?

java

add

arraylist

time-complexity