Алгоритмы

Амортизированный анализ: Худший случай - ложь

Цели урока

Понять когда worst-case анализ даёт неточную картину
Освоить три метода амортизированного анализа
Применить агрегатный метод к ArrayList
Знать амортизированные сложности популярных структур

Предварительные знания

Big O нотация
Space complexity

Python list, Java ArrayList, C++ vector используются в каждом проекте мира. PyTorch строит на них тензоры. Redis хранит так списки. Nginx держит так очереди соединений. И все три структуры имеют O(n) на вставку в worst-case. Этот парадокс разрешается одним понятием - амортизация.

**PyTorch/TensorFlow** - динамические массивы для параметров модели, resize при расширении батча
**Redis lists** - O(1) амортизированный append, RPUSH/LPUSH под нагрузкой
**Splay trees** - в сетевых маршрутизаторах Cisco для LRU-кеша маршрутов
**Union-Find** - Kruskal MST в алгоритмах построения spanning tree в сетях датацентров

Тарьян и рождение амортизации

В 1985 году Роберт Тарьян опубликовал статью «Amortized Computational Complexity» в SIAM Journal on Algebraic and Discrete Methods. Тарьян к тому моменту уже изобрёл Splay Trees (1985, совместно с Sleator) и улучшил Union-Find до почти-O(1). Именно эти структуры потребовали нового инструмента анализа - worst-case был бесполезен, average-case не давал гарантий. Амортизированный анализ стал третьим путём.

Когда worst-case врёт

**Python list, Java ArrayList, C++ vector** - три самые популярные структуры в индустрии. Все три имеют O(n) на вставку в худшем случае. Но PyTorch хранит параметры в таких списках. TensorFlow строит на них вычислительные графы. Ни один production-инженер не считает это проблемой.

Если вставка O(n), то n вставок = O(n²)? Но на практике - **линейно!** Это не трюк. Это математика, которую worst-case прячет.

Операция #	Размер	Что происходит	Стоимость
1	1->2	Resize + copy 1	2
2	2->4	Resize + copy 2	3
3-4	4	Просто вставка	2
5	4->8	Resize + copy 4	5
6-8	8	Просто вставка	3
9	8->16	Resize + copy 8	9

**Ключевое наблюдение:** дорогие операции (resize) случаются редко. Большинство вставок - дешёвые O(1). Worst-case смотрит на одну операцию. Амортизация смотрит на серию.

После 16 вставок в пустой ArrayList сколько раз произошёл resize (если начальный размер 1, рост x2)?

Идея амортизации

**Амортизированный анализ** - усреднение стоимости операций по серии. Даже если одна операция дорогая, в среднем каждая дешёвая. Adam optimizer в PyTorch обновляет миллиарды параметров. Каждый шаг - O(1). Но периодически происходит gradient clipping - дороже. Суммарная стоимость тренинга считается именно амортизированно.

**Амортизированная сложность != средний случай!** Это гарантированная верхняя граница для последовательности операций. Без вероятностей. Без предположений о входных данных.

**Три метода** амортизированного анализа:

**Aggregate (агрегатный)** - считаем общую стоимость n операций, делим на n
**Accounting (бухгалтерский)** - каждая операция платит фиксированную цену
**Potential (потенциалов)** - вводим функцию потенциала структуры данных

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

Агрегатный метод

**Aggregate method** - самый простой: считаем общую стоимость n операций, делим на n. Именно так считают latency p50/p99 в production - суммируют все запросы, делят. Один timeout не делает систему медленной, если сотни тысяч запросов дешёвые.

**Геометрическая прогрессия:** 1 + 2 + 4 + ... + n = 2n - 1. Это ключ к O(1) амортизации!

Если ArrayList растёт в 2 раза, после 1024 вставок сколько суммарно элементов было скопировано?

Бухгалтерский метод

**Accounting method** - назначаем каждой операции фиксированную «цену», которая может быть больше реальной стоимости. Избыток - «кредит» на будущее. Так работают сервисы с prepaid-моделью: Stripe берёт с каждой транзакции немного больше операционной стоимости, копит на покрытие редких chargeback-ов.

**Инвариант:** накопленный кредит >= 0 в любой момент. Если это выполняется, амортизированная оценка корректна.

В accounting method, если операция «дешевле» чем её амортизированная цена:

Метод потенциалов

**Potential method** - вводим функцию Phi (потенциал) структуры данных. Амортизированная стоимость = реальная + delta_Phi. Потенциал - как «накопленная энергия»: система заряжается на дешёвых операциях и разряжается на дорогих.

**Потенциал - это формализация кредита** из accounting method. Phi >= 0 гарантирует, что суммарная амортизированная стоимость >= реальной.

Потенциал структуры данных должен быть:

Примеры из реального мира

Амортизированный анализ - везде, где структура платит за будущее сейчас:

Структура	Операция	Worst-case	Амортизированная
ArrayList	append	O(n)	O(1)
Hash Table	insert	O(n)	O(1)
Splay Tree	find/insert	O(n)	O(log n)
Union-Find	union/find	O(log n)	O(alpha(n)) ~= O(1)
Fibonacci Heap	decrease-key	O(n)	O(1)
Deque (two stacks)	pop_front	O(n)	O(1)

**Union-Find** с path compression и union by rank имеет амортизированную сложность O(alpha(n)), где alpha - обратная функция Аккермана. Для всех практических n, alpha(n) <= 4.

**Осторожно:** амортизированный анализ не гарантирует, что КАЖДАЯ операция быстрая. Для real-time систем (игры, торговые платформы) отдельные O(n) операции могут быть неприемлемы - один resize во время обработки ордера стоит деньги.

Когда амортизированный анализ НЕ подходит?