java - 初始化数组列表的时间复杂度

Question

初始化数组列表的时间复杂度是多少？

Arraylist<E> A = new Arraylist<E>

关于:

Arraylist<Integer> B = new ArrayList<>(Arrays.asList(1,2,3,4,5)

对于第一个选项，我相信这将是 O(1) 常数时间。然而，第二个选择是我很难想到的。

Answer 1

Arrays.asList - 仅此一个将是O(1)。在底层，一个新的 ArrayList 是用给定的数组创建的 - 无论数组的大小如何。

或者更简单，无论数组的大小如何，相同的操作总是发生=它是恒定的。

当您执行new ArrayList(Arrays.asList...)时，它会在内部复制数据:

....
elementData = Arrays.copyOf(elementData, size, Object[].class);

最终将调用System::arrayCopy；这就是棘手的地方。一般来说，这可以被认为是O(n)，但由于这是一个 native 方法，因此可以作为单个 CPU 指令来实现；从而变成O(1)。

我仍然会选择O(n)作为答案。