Quelle est la complexité algorithmique de l'opération d'ajout d'un élément à la fin d'un ArrayList?

Добавление элемента в конец ArrayList в среднем имеет амортизированную сложность O(1). Это связано с тем, что при добавлении элемент просто помещается в следующую свободную ячейку массива.

Однако, если внутренний массив заполнен, происходит его расширение (обычно в 1.5-2 раза), что требует копирования всех элементов в новый массив. В этот момент операция добавления занимает O(n), где n — текущий размер списка.

Таким образом, амортизированная сложность добавления — O(1), но в худшем случае — O(n).