Какая сложность вставки в конец ArrayList и от чего она зависит?

Question

Вставка в конец ArrayList в среднем выполняется за O(1).Иногда операция может стоить O(n), если требуется расширение массива.При расширении происходит копирование элементов в новый массив.Однако такие операции редкие.Поэтому средняя (амортизированная) сложность считается константной.

YeaHub · Accepted Answer

Чтобы корректно ответить на вопрос, важно различать единичную и амортизированную сложность.Как работает вставка в конецОперация:list.add(value);
В обычном случае:Элемент записывается в следующий свободный индекс.Копирование данных не требуется.Сложность:O(1)Когда сложность становится O(n)Если внутренний массив заполнен:Создается новый массив большего размера.Все элементы копируются.Старый массив освобождается GC.// упрощенно
newCapacity = oldCapacity * 1.5
Копирование:O(n)Почему в среднем это O(1)Расширение:Происходит не при каждой вставке.Стоимость копирования «размазывается» по множеству операций.Это и называется:амортизированной сложностью O(1)Краткий выводВставка в конец ArrayList имеет амортизированную сложность O(1), но отдельные операции могут временно стоить O(n) из-за расширения массива.