Какова временная сложность вставки элемента в список (list) в Python?

Временная сложность вставки элемента в list в Python зависит от позиции вставки:

• Вставка в произвольное место (list.insert(i, x)): O(n)

  • Почему? При вставке элемента по индексу i все последующие n-i элементов должны быть сдвинуты на одну позицию вправо. В худшем случае, при вставке в начало списка (i=0), сдвигаются все n элементов.

• Добавление в конец (list.append(x)): Амортизированная O(1)

  • Почему? Обычно добавление в конец — это быстрая операция, так как Python резервирует дополнительную память. Однако, когда зарезервированное место заканчивается, список должен быть скопирован в новый, больший по размеру участок памяти. Эта редкая дорогостоящая операция (O(n)) "размазывается" по всем предыдущим быстрым вставкам, что в среднем дает константное время.

Пример:

my_list = [10, 20, 30, 40]

# O(n) - требует сдвига элементов 20, 30, 40
my_list.insert(0, 5)

# Амортизированная O(1) - обычно быстрая операция
my_list.append(50)

print(my_list) # [5, 10, 20, 30, 40, 50]

Вывод: Для частых вставок/удалений в начало или середину коллекции list неэффективен. В таких случаях лучше использовать collections.deque, который обеспечивает сложность O(1) для операций с обоих концов.