Зачем понадобилась «амортизированная» сложность

Возьмём list.append(x) в Python. Большинство туториалов скажут «это O(1)». Это правда — но не всегда. Иногда конкретный вызов append работает медленно, и иногда даже сильно медленно. Тем не менее в среднем на длинной серии вызовов он действительно O(1). Эта «средняя по серии» характеристика и называется амортизированная сложность.

Конкретно: если вы делаете 1 миллион lst.append(x), подавляющее большинство вызовов отрабатывает за наносекунды. Но редкие вызовы (раз в ~100 операций) делают неожиданно дорогую работу — могут занять микросекунды. Если усреднить — всё равно получится O(1) на операцию. Это и есть амортизированный O(1).

Разница между worst-case и amortized

Почему так — устройство list

Python list — это динамический массив. Реально в памяти лежит сплошной блок с указателями. У этого блока есть два размера:

• len — сколько элементов сейчас в списке (то, что возвращает len(lst)).
• capacity — сколько ещё может вместить без перевыделения.

Когда вы делаете append, происходит:

если len < capacity:
    положить x на позицию [len]
    len += 1
    # O(1)
иначе (массив полон):
    выделить новый блок размером capacity * growth_factor
    скопировать все len элементов туда
    освободить старый блок
    capacity = новый размер
    положить x, len += 1
    # O(n)

«Иногда дорогой» append случается только когда массив полон. После такого расширения у массива снова много свободного места — следующие N-1 append-ов снова дешёвые.

В CPython growth factor примерно 1.125 для больших списков (точнее формула чуть сложнее). Это означает: после увеличения capacity у нас есть N/8 свободных слотов, в которые мы делаем дешёвые append-ы перед следующей переаллокацией.

Банковский метод на пальцах

Самый понятный способ понять амортизированный анализ — банковский метод (он же accounting method). Идея простая: каждой операции мы приписываем некоторую «амортизированную стоимость» (фиктивную плату) — чуть больше, чем её реальная работа. «Излишек» откладываем на «счёт» как кредит. Когда происходит дорогая операция — оплачиваем её из накопленного счёта.

Применим к append. Предположим, growth factor 2 (для простоты — каждое расширение удваивает capacity):

1. Каждому append присваиваем амортизированную стоимость 3.
2. Реальная стоимость дешёвого append — 1 (положить элемент).
3. Излишек 2 — кладём на счёт элемента.

Когда массив капасити N полон и нужно расширение:

• Реальная стоимость расширения = N (скопировать все элементы).
• Но у нас уже есть N/2 элементов с накопленным счётом 2 каждый. Итого 2 * N/2 = N кредитов. Хватает.
• Счёт обнуляется, capacity удваивается до 2N. Опять начинаем накапливать.

Итог: каждый append «стоит» нам 3 операции амортизированно. То есть O(1) per operation. Дорогая операция расширения полностью оплачена заранее предыдущими дешёвыми.

Проверим эмпирически

Покажем «всплески» в реальном времени. Будем мерить время каждого отдельного append и смотреть, какие из них «дорогие»:

import time

def measure_appends(n):
    lst = []
    times = []
    for i in range(n):
        t0 = time.perf_counter_ns()
        lst.append(i)
        t1 = time.perf_counter_ns()
        times.append(t1 - t0)
    return times

times = measure_appends(100_000)

# Найдём 10 самых медленных вызовов и их индексы
slowest = sorted(enumerate(times), key=lambda p: -p[1])[:10]
for idx, t in slowest:
    print(f"append #{idx:>6}: {t:>6} ns")

# Среднее
print(f"\nMean: {sum(times) / len(times):.1f} ns")
print(f"Min:  {min(times)} ns")
print(f"Max:  {max(times)} ns")

Типичный вывод:

append #80000:   8500 ns
append #71000:   7100 ns
append #62000:   6300 ns
append #54000:   5500 ns
append #...      ...

Mean:   85 ns
Min:    40 ns
Max:  8500 ns

Видим: большинство append-ов работают за 40-100 ns. Но редкие — за тысячи ns. Эти всплески — точно те моменты, когда массив расширялся и копировал N элементов. Между всплесками — много-много дешёвых append-ов.

Среднее — 85 ns. Это и есть амортизированный O(1).

Capacity vs len в Python

Можно «подсмотреть» текущий capacity через sys.getsizeof. Размер списка — фиксированный header плюс capacity * 8 байт (указатели):

import sys

lst = []
prev_size = sys.getsizeof(lst)
for i in range(50):
    lst.append(i)
    sz = sys.getsizeof(lst)
    if sz != prev_size:
        # capacity = (sz - header) / 8
        # На 64-bit header обычно 56 байт
        capacity = (sz - 56) // 8
        print(f"len={len(lst):>3}, size={sz} bytes, capacity={capacity}")
        prev_size = sz

Типичный вывод (на Python 3.13):

len=  1, size=88 bytes, capacity=4
len=  5, size=120 bytes, capacity=8
len=  9, size=184 bytes, capacity=16
len= 17, size=248 bytes, capacity=24
len= 25, size=312 bytes, capacity=32
len= 33, size=376 bytes, capacity=40
len= 41, size=440 bytes, capacity=48

Видим: capacity растёт не точно в 2 раза. CPython использует формулу:

new_capacity = (current + (current >> 3) + 6) & ~3

(сдвиг на 3 = деление на 8, плюс 6, и округление к 4). Получается growth factor около 1.125 — экономнее, чем 2x в учебниках. Это и есть тот случай, когда реальная имплементация отличается от учебника, но амортизированный O(1) сохраняется — потому что суммарная работа всё равно линейна.

Не только append амортизируется

Амортизированный анализ работает и в других местах:

• list.pop() (из конца) — O(1) amortized.
• dict[key] = value — O(1) amortized (иногда нужна реаллокация хеш-таблицы).
• set.add(x) — O(1) amortized.
• str.join(list_of_str) — O(total length) amortized (внутри буфер растёт по той же логике).

А вот что не амортизируется:

• list.insert(0, x) — каждый раз O(n), не амортизируется.
• list.pop(0) — каждый раз O(n).
• x in list — O(n) каждый раз.

Когда амортизированный анализ ломается

Главное «но» — амортизация работает для средней по серии, не для каждого вызова. Иногда это важно:

• Realtime системы — если у вас latency-critical код, и нужна гарантия «каждая операция не дольше X микросекунд» — амортизированный O(1) не годится. Будет проседание в момент расширения.
• GC-паузы — расширение list-а может триггерить garbage collection, что добавит непредсказуемое время.

В DE-задачах это редко проблема (мы про throughput, не про latency), но в системах вроде high-frequency trading или embedded — пользуются специальными структурами с гарантированно O(1) операциями (например, fixed-size ring buffer).

Шпаргалка по амортизированному анализу

В следующем уроке — грабли big-O, которые встречаются в реальном коде. Скрытые O(n) внутри встроенных операций, ловушки конкатенации строк, проблема копирования slices.