Ответ
Амортизированная сложность — O(1).
Объяснение:
- Обычный случай (O(1)): Если во внутреннем массиве есть свободная емкость (
size < capacity), элемент просто помещается в следующую ячейку. - Случай расширения (O(n)): Если массив заполнен, происходит реаллокация: создается новый массив большего размера (обычно
capacity * 1.5), и все существующие элементы копируются в него. Эта операция имеет сложность O(n).
Так как дорогостоящее расширение происходит редко, средняя стоимость добавления одного элемента (амортизированная) остается константной — O(1).
Пример:
ArrayList<Integer> list = new ArrayList<>(3); // capacity = 3
list.add(1); // O(1)
list.add(2); // O(1)
list.add(3); // O(1)
list.add(4); // O(n) - происходит расширение массива и копирование 3 элементов
// Последующие добавления снова будут O(1), пока не заполнится новая capacity.