Какова сложность вставки элемента в список?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

Списки в Python реализованы как динамические массивы. Это значит, что они хранят элементы в непрерывном блоке памяти. Такая структура позволяет быстро получать доступ к элементам по индексу, но накладывает некоторые ограничения на операции вставки и удаления.

Вставка элемента в конец списка

Когда вы добавляете элемент в конец списка с помощью метода append(), Python обычно просто добавляет элемент в конец массива. Если в массиве достаточно места, эта операция выполняется за постоянное время O(1). Однако, если массив заполнен, Python выделяет новый, более крупный блок памяти, копирует в него элементы старого массива и затем добавляет новый элемент. Этот процесс называется "ресайзинг" и происходит нечасто, поэтому средняя амортизированная сложность вставки в конец списка остается O(1).

Вставка элемента в произвольную позицию

Если вы хотите вставить элемент в произвольную позицию списка, например, с помощью метода insert(index, element), Python должен сдвинуть все элементы, начиная с указанного индекса, на одну позицию вправо, чтобы освободить место для нового элемента. Это требует перемещения всех последующих элементов, что делает сложность операции линейной, O(n), где n — количество элементов, которые нужно сдвинуть.

Пример

# Создаем список
my_list = [1, 2, 3, 4, 5]
​
# Вставка в конец
my_list.append(6)  # O(1)
​
# Вставка в середину
my_list.insert(2, 'a')  # O(n)