Сложность времени конструктора Java ArrayList

Question

Я изучаю класс ArrayList как часть школьного проекта.

В документах API Java API на сайте Oracle упоминается, что все операции, за исключением заданных, являются «примерно линейным временем».

Конструкторы не перечислены в рамках данного мало, но я с трудом, видя, как это:

public ArrayList(int initialCapacity) { 
     if (initialCapacity > 0) { 
      this.elementData = new Object[initialCapacity]; 
     } else if (initialCapacity == 0) { 
      this.elementData = EMPTY_ELEMENTDATA; 
     } else { 
      throw new IllegalArgumentException("Illegal Capacity: "+ 
               initialCapacity); 
     } 
} 

является линейное время. Я что-то упустил?

Answer 1

Это линейная, так как декларация массива О (п), как указано в этом вопросе: Java: what's the big-O time of declaring an array of size n?

Answer 2

В коде вы разместили, один из 3-х вещей происходит.

1. если initialCapacity>0, elementData = new Object[initialCapacity];

2. если initialCapacity==0, elementData = EMPTY_ELEMENTDATA;

3. если initialCapacity<0, бросить исключение.

Все эти операции, за номер 1, за исключением, принимать постоянного время, так как не требуется итерация по коллекции.

Номер 1 принимает линейное время, потому что объявление массива размера n занимает время O (n). Я не буду переписывать всю причину, так как на этом месте есть сообщение о SO. Общая идея: это происходит потому, что пространство должно быть выделено для каждого из элементов n.

Я надеюсь на помощь. :)