java - Arraylist时间复杂度: do you copy over and shift elements as needed at the same time?

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 是根据最坏情况定义的，而添加到数组列表的最坏情况涉及调整大小，从而将所有元素复制到新数组中。我认为方法 2 的复杂度为 O(n^2)，因为对于数组中的每个元素，您可能必须将所有元素复制到更大的数组中。

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

Answer 1

ArrayList 由数组支持。如果在数组的头部“插入”一个元素，则必须将所有其他元素向右移动 1 以腾出空间。这意味着一次调用:

list.add(0, i);

的复杂度为O(n)，因为每个元素(已添加)都必须移动。
如果执行此操作 n 次，则时间复杂度为 O(n^2)。

但是将一个元素添加到(支持)数组的末尾:

list.add(i);

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

如果您执行 O(1) 的操作，除了每 log n 次 O(n) 次，n 次，即 O(n log n)。