Какая алгоритмическая сложность вставки объекта в список в Python?

Алгоритмическая сложность вставки в список Python

Краткий ответ

Вставка элемента в произвольное место списка — O(n), где n — количество элементов.

Подробное объяснение

1. Вставка в конец (append)

my_list = [1, 2, 3]
my_list.append(4)  # O(1) амортизованная сложность

# Python переаллоцирует память только когда нужно
# Обычно переаллокация происходит в 1.125 раза

Сложность: O(1) амортизированная

2. Вставка в начало или середину

my_list = [1, 2, 3, 4, 5]

# Вставка в начало
my_list.insert(0, 0)  # [0, 1, 2, 3, 4, 5]
# Нужно сдвинуть все 5 элементов
# Сложность: O(n)

# Вставка в середину
my_list.insert(3, 99)  # [0, 1, 2, 99, 3, 4, 5]
# Нужно сдвинуть элементы с индекса 3 до конца (5 элементов)
# Сложность: O(n - i), где i — позиция вставки

# Вставка в конец (явная через insert)
my_list.insert(len(my_list), 100)  # [0, 1, 2, 99, 3, 4, 5, 100]
# Сложность: O(1) — не нужно сдвигать элементы

Сложность зависит от позиции:

• В конец: O(1)
• В начало: O(n)
• В позицию i: O(n - i)

Почему O(n)?

Потому что Python хранит список как динамический массив (contiguous memory):

# Внутреннее представление
# [1, 2, 3, 4, 5]  <- список в памяти
#  0  1  2  3  4   <- индексы

# При вставке 99 в позицию 2:
my_list = [1, 2, 3, 4, 5]
my_list.insert(2, 99)

# Шаг 1: Найти позицию
# Шаг 2: Сдвинуть элементы [3, 4, 5] на одну позицию вправо
#        [1, 2, _, 3, 4, 5]  <- нужны O(3) операции
# Шаг 3: Вставить элемент
#        [1, 2, 99, 3, 4, 5]

Практический пример с измерением

import timeit

# Вставка в конец (O(1))
setup1 = "lst = list(range(10000))"
stmt1 = "lst.append(99999)"
time1 = timeit.timeit(stmt1, setup1, number=10000)

# Вставка в начало (O(n))
setup2 = "lst = list(range(10000))"
stmt2 = "lst.insert(0, -1)"
time2 = timeit.timeit(stmt2, setup2, number=10000)

print(f"append (O(1)): {time1:.4f}s")
print(f"insert(0) (O(n)): {time2:.4f}s")
print(f"Разница: {time2/time1:.1f}x медленнее")
# Результат: insert примерно в 1000x медленнее!

Сравнение разных операций

import timeit

operation_complexities = {
    "append": {"stmt": "lst.append(99)", "complexity": "O(1)"},
    "insert(0)": {"stmt": "lst.insert(0, 99)", "complexity": "O(n)"},
    "insert(len//2)": {"stmt": "lst.insert(len(lst)//2, 99)", "complexity": "O(n)"},
    "extend": {"stmt": "lst.extend([99, 100])", "complexity": "O(k)"},
}

for name, info in operation_complexities.items():
    setup = "lst = list(range(10000))"
    time = timeit.timeit(info["stmt"], setup, number=1000)
    print(f"{name:20} | {info['complexity']:6} | {time:.5f}s")

Таблица сложностей для списка

Как улучшить производительность

1. Используй deque для вставки в начало

from collections import deque

# Неправильно (O(n))
my_list = [1, 2, 3]
my_list.insert(0, 0)  # Медленно

# Правильно (O(1))
my_deque = deque([1, 2, 3])
my_deque.appendleft(0)  # Быстро!

# Сравнение
import timeit

list_time = timeit.timeit(
    "lst.insert(0, 0)",
    "lst = list(range(10000))",
    number=1000
)

deque_time = timeit.timeit(
    "dq.appendleft(0)",
    "from collections import deque; dq = deque(range(10000))",
    number=1000
)

print(f"List: {list_time:.4f}s")
print(f"Deque: {deque_time:.4f}s")
print(f"Deque в {list_time/deque_time:.0f}x быстрее")

2. Накопи данные и добавь разом

# Неправильно (O(n*k) где k — количество вставок)
result = []
for i in range(1000):
    result.insert(0, i)  # O(n) каждый раз!

# Правильно (O(n))
result = []
for i in range(1000):
    result.append(i)
result.reverse()  # O(n) одна операция

# Или используй deque
from collections import deque
result = deque()
for i in range(1000):
    result.appendleft(i)  # O(1) каждый раз!

3. Предварительно выдели место

# Если знаешь финальный размер
result = [None] * 1000  # Выдель память один раз
for i in range(1000):
    result[i] = i  # O(1) присваивание

# Вместо
result = []
for i in range(1000):
    result.append(i)  # О(1) амортизированная, но может быть переаллокация

Ключевые моменты

1. append — O(1) амортизированная
2. insert — O(n) в среднем, зависит от позиции
3. Причина: Python хранит список как динамический массив
4. Решение: Используй deque для вставки в начало
5. Важно: Избегай циклических insert(0, x) — это O(n²)!