Что такое амортизированная сложность?

Некоторые структуры данных иногда выполняют дорогую операцию, но так редко, что в сумме по серии стоимость на одну операцию остаётся маленькой.

Классический пример — динамический массив (list в Python, ArrayList в Java, vector в C++). Пока есть свободное место, добавление в конец — O(1). Когда место кончилось, выделяется массив вдвое больше и все элементы копируются — O(n). Посчитаем суммарную работу для n добавлений: копирования происходят при размерах 1, 2, 4, 8, …, n, их сумма меньше 2n. Плюс n простых вставок. Итого меньше 3n операций на n добавлений, то есть O(1) на операцию в среднем по серии.

Важно, что массив растёт в разы. Если бы он увеличивался на 10 элементов, копирований было бы n/10, каждое до n элементов — итого O(n²) на серию, O(n) на операцию.

Отличие от средней сложности: средняя считается по распределению входных данных (например, хеш-таблица при «хорошем» хеше). Амортизированная — это гарантия для любой последовательности операций, без вероятностей.

Другие примеры: расширение хеш-таблицы, очередь на двух стеках, система непересекающихся множеств (union-find).

import sys

a = []
prev = sys.getsizeof(a)
for i in range(20):
    a.append(i)
    size = sys.getsizeof(a)
    if size != prev:        # память выделяется скачками, а не на каждый append
        print(f"после {len(a)} элементов: {size} байт")
        prev = size