¿Cuál es la complejidad de insertar al final de una lista (lista de Python)? ¿Por qué a veces O(n)?

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

Однако иногда операция занимает O(n), когда текущий выделенный буфер заполнен, и требуется выделить новый массив большего размера и скопировать туда все элементы. Это копирование и приводит к линейной сложности в этот момент.

Пример:

lst = [1, 2, 3]
lst.append(4)  # Обычно O(1)

Но если внутренний буфер заполнен, Python выделит новый массив, скопирует старые элементы и добавит новый — это O(n).