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

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

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

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

Для большинства операций добавления элемента в конец список имеет уже выделенную память. Это означает, что операция выполняется в константное время:

my_list = [1, 2, 3]  # Внутренняя ёмкость > 3
my_list.append(4)    # O(1) — просто добавляем в конец
my_list.append(5)    # O(1) — просто добавляем в конец

Переполнение буфера: O(n) в худшем случае

Когда список переполняется и требуется расширение, Python создаёт новый больший массив и копирует все элементы. Это берёт O(n) времени:

my_list = []  # Ёмкость: 0
my_list.append(1)  # Расширение! Копируем старые элементы (нет их), O(1)
my_list.append(2)  # O(1) — есть свободное место
my_list.append(3)  # O(1)
my_list.append(4)  # Переполнение! Расширение → O(n)
my_list.append(5)  # O(1) — есть свободное место
my_list.append(6)  # O(1)
my_list.append(7)  # O(1)
my_list.append(8)  # O(1)
my_list.append(9)  # Переполнение! Расширение → O(n)

Как работает расширение списка в Python

Python использует стратегию переросла (over-allocation). При переполнении размер увеличивается примерно на 25% (точно: new_size = size + size // 8 + 6 для больших размеров):

import sys

my_list = []
print(f"Начальная ёмкость: {sys.getsizeof(my_list)}")

# Наблюдаем, как растёт ёмкость при append()
for i in range(10):
    my_list.append(i)
    print(f"После добавления {i+1} элемента, объём в байтах: {sys.getsizeof(my_list)}")

Вывод будет показывать скачки при переполнении.

Амортизированный анализ

Именно благодаря этой стратегии over-allocation, даже с учётом O(n) операций расширения, амортизированная сложность остаётся O(1).

Математическое объяснение:

• Если у нас есть n операций append()
• И список расширяется каждый раз в ~1.25 раз
• То количество операций расширения ≈ log(n)
• Каждое расширение копирует i элементов (где i растёт: 1, 2, 4, 8...)
• Общая стоимость: 1 + 2 + 4 + 8 + ... + n = O(n)
• Для n операций: O(n) / n = O(1) амортизированно

# Пример амортизированного анализа
operations = 0
my_list = []

for i in range(1000):
    my_list.append(i)  # Каждый append может быть O(1) или O(n)
    # Но в среднем это O(1)

print(f"В среднем: {operations / 1000} операций на append()")

Практическое значение

Для практического программирования это означает:

# ✅ Это эффективно — O(n) амортизированно
result = []
for item in range(1_000_000):
    result.append(item)

# ❌ Это очень неэффективно — O(n²)
result = []
for item in range(1_000_000):
    result.insert(0, item)  # Вставка в начало = O(n)

# ✅ Это эффективно для конца
result = []
for item in range(1_000_000):
    result.append(item)  # O(1) амортизированно

Сравнение операций со списком

Внутренняя структура

Это помогает понять, почему append() быстро:

# Упрощённое представление
class SimpleList:
    def __init__(self):
        self.capacity = 10      # Выделенное место
        self.size = 0           # Актуальное количество элементов
        self.data = [None] * 10 # Внутренний массив
    
    def append(self, value):
        if self.size >= self.capacity:
            # Расширяем (редко)
            self.capacity = int(self.capacity * 1.25)
            new_data = [None] * self.capacity
            for i in range(self.size):
                new_data[i] = self.data[i]  # O(n)
            self.data = new_data
        
        # Добавляем в конец (обычно)
        self.data[self.size] = value  # O(1)
        self.size += 1

Альтернативы для разных сценариев

# Если нужна вставка в начало — используйте deque
from collections import deque

q = deque()
q.appendleft(1)  # O(1)
q.appendleft(2)  # O(1)

# Если нужна вставка в середину — используйте дерево или другую структуру
# Но обычно это редко требуется

Вывод

Главное правило: вставка в конец списка — это O(1) амортизированно. Иногда (редко) это O(n) при расширении, но в среднем это очень эффективная операция. Поэтому append() — ваш лучший друг при работе со списками в Python!

Именно это делает список таким популярным и эффективным для большинства задач.