Временная сложность инициализации массива

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), но, поскольку это собственный метод, он может быть реализован в виде одной инструкции CPU;таким образом, став O(1).

, я бы все равно пошел с O(n) в качестве ответа.