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

Question

Является ли ArrayList массивом или списком в Java? какова временная сложность операции get: O(n) или O(1)?

Answer 1

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)) также постоянное время)

Answer 2

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

Джавадок говорит:

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

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