Qual è la complessità dell'inserimento alla fine di una lista (lista Python)? Perché a volte è O(n)?

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

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

Пример:

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

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