Какая сложность операций append, pop, insert для list в Python?

Временная сложность операций list в Python

Основные операции и их сложность

Почему append O(1) амортизированная?

Механизм динамического массива в CPython:

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

lst = []  # capacity = 0, size = 0
lst.append(1)  # capacity = 1, size = 1
lst.append(2)  # capacity = 2, size = 2 (reallocate)
lst.append(3)  # capacity = 4, size = 3 (reallocate, grow by 1.125x)
lst.append(4)  # capacity = 4, size = 4
lst.append(5)  # capacity = 8, size = 5 (reallocate)

Формула роста: Когда нужна реаллокация, новая ёмкость = old_capacity + (old_capacity >> 3) + 3

Это означает:

• Большую часть времени append работает за O(1)
• Редко происходит реаллокация за O(n)
• В среднем (амортизированная сложность) это O(1)

Экспериментальная проверка

import time

# Проверка append - O(1)
lst = []
start = time.time()
for _ in range(100_000_000):
    lst.append(1)
append_time = time.time() - start
print(f"append время: {append_time:.2f}s")

# Проверка insert(0, x) - O(n)
lst = list(range(1_000_000))
start = time.time()
for _ in range(100):
    lst.insert(0, 999)
insert_time = time.time() - start
print(f"insert(0, x) время: {insert_time:.2f}s")  # Намного медленнее!

# Проверка pop() - O(1)
lst = list(range(10_000_000))
start = time.time()
for _ in range(1_000_000):
    lst.pop()
pop_time = time.time() - start
print(f"pop() время: {pop_time:.2f}s")

# Проверка pop(0) - O(n)
lst = list(range(1_000_000))
start = time.time()
for _ in range(100):
    lst.pop(0)
pop0_time = time.time() - start
print(f"pop(0) время: {pop0_time:.2f}s")  # Медленнее!

Практические последствия

Хорошо (быстро):

# O(1) - append в конец
stack = []
for item in items:
    stack.append(item)
value = stack.pop()

Плохо (медленно):

# O(n) для каждой операции - queue на list!
queue = []
for item in items:
    queue.append(item)
value = queue.pop(0)  # Медленно! O(n) каждый раз

Правильное решение:

from collections import deque

# O(1) для обеих операций
queue = deque()
for item in items:
    queue.append(item)
value = queue.popleft()  # O(1)!

Когда какая структура нужна?

# Stack (LIFO) - используй list
stack = []
stack.append(value)      # O(1)
value = stack.pop()      # O(1)

# Queue (FIFO) - используй deque
from collections import deque
queue = deque()
queue.append(value)      # O(1)
value = queue.popleft()  # O(1)

# Случайный доступ - используй list
arr = [1, 2, 3, 4, 5]
print(arr[2])            # O(1)

# Частые вставки в начало/середину - используй LinkedList
# Но в Python нет встроенного LinkedList
# Используй list только если вставляешь в конец

Внутреннее устройство list

# CPython использует C-массив указателей на объекты Python
# Структура примерно так:

class PyListObject:
    ob_item = None  # C-массив указателей на объекты
    allocated = 0   # Выделенная ёмкость
    ob_size = 0     # Текущий размер

# При append:
# 1. Проверяем: ob_size < allocated
# 2. Если да: добавляем элемент за O(1)
# 3. Если нет: выделяем новый больший массив и копируем (O(n))

Ключевые правила для интервью

1. append() = O(1) амортизированная, а не O(n)
2. pop() = O(1), но pop(i) = O(n)
3. insert(0, x) = O(n) - худший случай
4. Используй deque для очередей, не list
5. list[i:j] копирует подсписок - O(j-i)
6. remove(), index() = O(n) - требуют поиска

Трюк: Асимптотическая запись

Можно ответить на вопрос так:

"append() работает за O(1) в среднем благодаря динамическому росту ёмкости. При реаллокации это O(n), но так как число реаллокаций растёт логарифмически, итоговая сложность n операций append остаётся O(n), то есть O(1) в амортизированном смысле".