Сложность времени для Java ArrayList

Ответ 1

An ArrayList в Java - это List, который поддерживается array.

Метод get(index) - это постоянное время, O(1), операция.

Код прямо из библиотеки Java для ArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

В принципе, он просто возвращает значение прямо из массива поддержки. (RangeCheck(index)) также является постоянным временем)

Ответ 2

Реализация выполняется с помощью массива, а операция get - O (1).

javadoc говорит:

Размер, isEmpty, get, set,  итератор и операции listIterator выполняются в постоянных  время. Операция add работает в амортизированном постоянном времени,  т.е. для добавления n элементов требуется время O (n). Все остальные операции  работать в линейном времени (грубо говоря). Постоянный коэффициент низкий  к этому для реализации LinkedList.

Ответ 3

Как уже отмечалось, операции чтения - это постоянное время - O (1), но операции записи могут выходить из пространства в массиве резервных копий, перераспределять и копировать - чтобы он работал в O ( n) время, как гласит документ:

Размер, isEmpty, get, set, iterator, и операции listIterator выполняются в постоянное время. Выполняется операция добавления в амортизированном постоянном времени, то есть, добавление n элементов требует O (n) времени.Все остальные операции выполняются в линейное время (грубо говоря). постоянный коэффициент низкий по сравнению с что для LinkedList реализация.

На практике все O (1) после нескольких добавлений, так как массив поддержки удваивается каждый раз, когда его мощность исчерпана. Поэтому, если массив начинается с 16, он заполняется, он перераспределяется до 32, затем 64, 128 и т.д., Поэтому он масштабируется нормально, но GC может поражать во время большого realloc.

Ответ 4

Чтобы быть педантичным, это a List, поддерживаемый массивом. И да, сложность времени для get() равна O (1).

Ответ 5

Просто примечание.

Метод get(index) - это постоянное время, O(1)

Но это случай, если мы знаем индекс. Если мы попытаемся получить индекс с помощью indexOf(something), это будет стоить O(n)