Амортизированная сложность

Амортизированная сложность ограничивает среднюю стоимость операции по любой последовательности операций, даже если отдельный вызов иногда дорогой. Она не опирается на вероятностное распределение входов: дорогие события оплачиваются множеством дешёвых.

Зачем это на интервью

Тема нужна, чтобы корректно объяснить рост динамического массива, batch-операции и всплески latency. Ответ «append — $O(1)$» неполон: обычно это амортизированное $O(1)$, а конкретный append при росте capacity может копировать элементы и быть $O(n)$.

Минимум для E4

• Отличать стоимость одной операции от стоимости последовательности.
• Объяснять рост динамического массива и копирование при resize.
• Не путать амортизированную стоимость с ожидаемой.
• Учитывать пиковую память во время копирования.

Пусть capacity массива растёт геометрически. При заполнении выполняются копирования размера примерно $1,2,4,\dots ,n$; их сумма меньше постоянного множителя $n$. Поэтому $n$ добавлений стоят $O(n)$ суммарно, то есть амортизированно $O(1)$ на добавление. Но единичная операция resize остаётся линейной по числу копируемых элементов.

Углубление для E5/Senior

Для продакшена амортизация не гарантирует отсутствие выброса latency. Resize на горячем пути способен одновременно вызвать копирование, аллокацию и рост GC pressure; lock вокруг такой структуры переносит паузу на конкурирующих клиентов. E5 отделяет среднюю пропускную способность от SLA одной операции: заранее резервирует ёмкость, дробит работу или переносит перестройку из критического пути, если p99 важнее средней стоимости.

Доказательства применяют по методу агрегирования, бухгалтерскому методу или потенциальной функции. Бухгалтерский метод мысленно кладёт «кредит» на дешёвую операцию для оплаты будущего resize; это не реальные деньги и не утверждение, что каждая операция физически одинаково быстра. Конкретная стратегия роста slice — деталь реализации runtime, поэтому код не должен зависеть от точного коэффициента роста capacity.

Ключевые понятия

• Амортизированная стоимость — суммарная стоимость худшей последовательности из $m$ операций, делённая на $m$.
• Resize — выделение нового буфера и перенос части или всех элементов при нехватке capacity.
• Геометрический рост — увеличение capacity с постоянным коэффициентом; даёт линейную сумму копирований.
• Пиковая память — старый и новый буферы могут существовать одновременно, пока копирование не завершено.
• Ожидаемая сложность — утверждение о вероятности; она отличается от амортизированной гарантии на последовательности.
• Preallocation — заранее выделенная ёмкость, уменьшающая resize, но рискующая неиспользованной памятью.

Типовые вопросы

1. Почему append в динамический массив амортизированно $O(1)$?
   • Геометрический рост делает суммарное число скопированных элементов за $n$ добавлений $O(n)$; деление на $n$ даёт $O(1)$.
2. Бывает ли append $O(n)$?
   • Да. Когда capacity недостаточна, реализация может выделить новый массив и скопировать текущие элементы.
3. Чем амортизированное отличается от среднего случая?
   • Амортизация ограничивает последовательность операций без распределения вероятностей; средний случай требует предположений о входе.
4. Всегда ли стоит использовать make([]T, 0, n)?
   • Только когда разумна оценка $n$ и память приемлема. Сильно завышенная ёмкость увеличивает удерживаемый heap.
5. Почему resize опасен для p99?
   • Редкая линейная операция может попасть в запрос пользователя, увеличить паузу под lock и добавить давление на GC.
6. Можно ли полагаться на точный рост capacity у Go slice?
   • Нет. Это деталь реализации, меняющаяся между версиями и зависящая от размера элемента; контракт — семантика append, не коэффициент роста.

Практика

• Напишите benchmark добавления $10^3$, $10^5$ и $10^6$ элементов в slice с make([]int, 0) и с точной начальной capacity. Готово: результаты включают ns/op, B/op, allocs/op, одинаковый объём данных и вывод о trade-off памяти.
• Зафиксируйте редкий дорогой append. Готово: программа выводит изменения len и cap, а в объяснении отдельно названы амортизированная и единичная стоимости.
• Спроектируйте буфер для batch-отправки. Готово: указаны максимальный размер batch, политика переполнения, ограничение памяти и метрика для проверки p99.

Частые ошибки и ловушки

• Говорить «всегда $O(1)$» и скрывать resize.
• Приписывать Go фиксированный коэффициент роста capacity как публичный контракт.
• Предвыделять capacity по верхнему лимиту для каждого запроса и удерживать лишнюю память.
• Использовать общую растущую структуру под lock в latency-critical пути без измерения конкуренции.
• Делать вывод о p99 только по амортизированной сложности.

Связанные темы

Производительность и память · Big O · Аллокации и GC · Хвостовые задержки

Источники

• Thomas H. Cormen et al., Introduction to Algorithms, раздел об амортизированном анализе.
• Robert Sedgewick and Kevin Wayne, Algorithms, раздел о resizing arrays.
• Go project, The Go Programming Language Specification, разделы append и make.
• Go project, исходный код runtime, реализация роста slice как не-контрактная деталь.