Какая алгоритмическая сложность вставки значений в середину списка?

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

Вставка значений в середину списка — одна из самых частых операций в программировании. Понимание её сложности критично для выбора правильной структуры данных.

Динамический массив (list в Python) — O(n)

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

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

# Вставка в позицию 2 (между 2 и 3)
my_list.insert(2, 99)  # O(n)
print(my_list)  # [1, 2, 99, 3, 4, 5]

# Почему O(n)?
# 1. Находим позицию: O(1)
# 2. Сдвигаем все элементы справа на одну позицию: O(n - i)
# 3. Вставляем новый элемент: O(1)

# При вставке в конец — O(1) amortized
my_list.append(6)  # O(1)

# При вставке в начало — O(n) worst case
my_list.insert(0, 0)  # O(n)

# При вставке в середину — O(n) worst case
my_list.insert(len(my_list)//2, 50)  # O(n)

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

import time

# Демонстрация: вставка в начало vs конец
my_list = list(range(100000))  # 100k элементов

# Вставка в конец — быстро
start = time.perf_counter()
my_list.append(999999)
end = time.perf_counter()
print(f"Append (конец): {(end-start)*1e6:.2f} микросекунд")  # ~0.5 мкс

# Вставка в начало — медленно
my_list = list(range(100000))
start = time.perf_counter()
my_list.insert(0, -1)
end = time.perf_counter()
print(f"Insert (начало): {(end-start)*1e6:.2f} микросекунд")  # ~1000+ мкс

Связный список (deque в Python) — O(1) или O(n)

Добавление в начало или конец — O(1). Добавление в середину — O(n).

from collections import deque

my_deque = deque([1, 2, 3, 4, 5])

# Вставка в конец: O(1)
my_deque.append(6)

# Вставка в начало: O(1)
my_deque.appendleft(0)

print(my_deque)  # deque([0, 1, 2, 3, 4, 5, 6])

# Вставка в середину: O(n) — нужно перейти к нужной позиции
my_list = list(my_deque)
my_list.insert(3, 99)
my_deque = deque(my_list)

# deque быстрее для операций в начале/конце, но медленнее для доступа по индексу
start = time.perf_counter()
value = my_deque[50000]  # O(n) — линейный поиск
end = time.perf_counter()
print(f"Доступ по индексу [50000]: {(end-start)*1e6:.2f} мкс")  # медленно

Сбалансированное дерево поиска (например, TreeMap) — O(log n)

Если нужна вставка с сохранением сортировки, дерево поиска даёт O(log n).

from sortedcontainers import SortedList

sorted_list = SortedList([1, 3, 5, 7, 9])

# Вставка в отсортированный список: O(log n) поиск + O(n) сдвиг
# Но общая сложность остаётся O(n) из-за сдвига
sorted_list.add(4)  # Вставляется между 3 и 5
print(sorted_list)  # SortedList([1, 3, 4, 5, 7, 9])

# Для BST (Binary Search Tree) с балансировкой (AVL, Red-Black):
# Поиск позиции: O(log n)
# Вставка узла: O(log n)
# Перебалансировка: O(log n)
# Итого: O(log n)

Хеш-таблица (dict) — O(n) в худшем случае

Для добавления нового элемента — O(1) amortized, но может потребоваться rehash всей таблицы.

my_dict = {1: 'a', 2: 'b', 3: 'c'}

# Добавление: O(1) в среднем
my_dict[4] = 'd'  # O(1)

# Удаление: O(1) в среднем
del my_dict[1]  # O(1)

# При заполнении более чем на 75%, хеш-таблица автоматически увеличивается
# Это требует O(n) для rehash всех элементов
# Но это происходит редко, поэтому амортизированная сложность O(1)

Таблица сложностей для основных операций

*Если уже знаем позицию (есть указатель) **Только в начало или конец

Практические примеры

Проблема: вставляем 1000 элементов в список из 100000 элементов в начало

big_list = list(range(100000))

# Неправильный способ: O(n*m) где n=100000, m=1000
start = time.perf_counter()
for i in range(1000):
    big_list.insert(0, -i)  # O(n) каждый раз!
end = time.perf_counter()
print(f"Неправильно: {end-start:.3f} сек")  # Очень медленно!

# Правильный способ 1: используем deque для операций в начале
from collections import deque
big_deque = deque(range(100000))

start = time.perf_counter()
for i in range(1000):
    big_deque.appendleft(-i)  # O(1)
end = time.perf_counter()
print(f"С deque: {end-start:.6f} сек")  # Очень быстро!

# Правильный способ 2: сначала готовим данные, потом объединяем
new_elements = list(range(-1000, 0))
big_list = new_elements + big_list  # O(n) один раз, лучше
print(f"Объединение: O(n)")

Рекомендации по выбору структуры данных

Используй list (динамический массив) если:

• Нужен частый доступ по индексу O(1)
• Вставки в конец (append) O(1) amortized
• Нет вставок в начало/середину

Используй deque если:

• Нужны операции в начале и конце O(1)
• Редко нужен доступ по индексу
• Вставляем в начало/конец, не в середину

Используй SortedList если:

• Нужна отсортированность
• Нужен бинарный поиск
• Вставки редки (не критична производительность)

Используй dict если:

• Нужен быстрый поиск O(1) по ключу
• Порядок элементов не важен (Python 3.7+ сохраняет порядок вставки)

Главное правило: перед выбором структуры данных профилируй и измеряй реальные операции, которые будут выполняться.