Амортизация: цена, размазанная по серии

Если понимаешь, чем амортизированная цена отличается от среднего случая, и умеешь считать агрегатным методом, листай до «Теперь сам».

Как думаешь, дорога ли вставка в динамический массив

Динамический массив при заполнении заводит буфер в несколько раз больше (для наглядности возьмём удвоение) и копирует всё старое - одна такая вставка стоит Θ(n). Кажется, вставка дорогая. Но удвоения редки: между ними идут дешёвые вставки за O(1). Если считать не одну вставку, а тысячу подряд, дорогих среди них единицы. Средняя по серии выходит O(1) - и амортизированный анализ это доказывает строго.

На что это похоже

Слово пришло из бухгалтерии: крупную покупку (станок) не вешают на один месяц, а РАЗМАЗЫВАЮТ по всему сроку службы. Станок за миллион, работающий десять лет, - это не «миллион в марте», а «сто тысяч в год». Так же и дорогая операция: её цену размазывают по всем дешёвым, что идут рядом. Отчёт за год ровный, хотя платёж был разовый.

Механизм: агрегатный метод

Самый прямой способ. Считаешь общую цену n операций в худшем случае - T(n) - и делишь на n. Результат T(n)/n и есть амортизированная цена одной операции. Вся хитрость в том, чтобы честно сложить дорогие и дешёвые вместе, а не брать максимум по одной.

Возьмём n вставок в пустой массив с удвоением. Дешёвая часть: каждая вставка кладёт один элемент - это n. Дорогая часть: копирования при удвоениях. Удвоения случаются на размерах 1, 2, 4, ... (не больше n), и на каждом копируется столько элементов, каков размер. Их сумма - геометрический ряд, где последний член не больше n, а весь ряд 1 + 2 + 4 + ... ≤ 2n − 1 < 2n (из главы про суммы). Итого T(n) < n + 2n = 3n, то есть Θ(n) на всю серию. Делим на n: амортизированная цена вставки Θ(n)/n = O(1).

Правило

Амортизированная цена - средняя по серии из n операций в ХУДШЕМ случае, без вероятности. Агрегатный метод: амортизированная цена = T(n)/n, где T(n) - общая цена всей серии. Дорогая операция не делает дорогой всю серию, если дорогие редки и «оплачены» соседними дешёвыми.

Разбор: это НЕ средний случай

Легко спутать с средним случаем из прошлого раздела, но это разные вещи. Средний случай - ожидание по СЛУЧАЙНЫМ входам, и там есть вероятность и «неудачный вход». Амортизированный анализ вероятностей не знает вовсе: он берёт САМУЮ ПЛОХУЮ серию операций и всё равно получает малую среднюю. Гарантия сильнее: не «в среднем по удаче», а «по любой серии, даже худшей». Поэтому амортизированную оценку можно давать там, где средней доверять нельзя - никакой противник не подберёт серию, на которой n вставок обойдутся дороже Θ(n).

Разбор: двоичный счётчик

Второй классический пример - счётчик, который увеличивают на единицу n раз. Одно увеличение в худшем случае переворачивает все биты (...0111 + 1 = ...1000, k переворотов). Кажется, цена Θ(log n) за раз. Но агрегатно: бит 0 переворачи‐ вается каждый раз (n), бит 1 - через раз (n/2), бит 2 - вчетверо реже (n/4), и так далее. Всего переворотов n + n/2 + n/4 + ... < 2n - опять геометрический ряд. На n увеличений Θ(n) переворотов, значит O(1) на одно увеличение амортизированно, а не Θ(log n).

Разбор: восемь вставок по шагам

Проследим серию из восьми вставок в массив, который удваивается при заполнении (начальная ёмкость 1):

вставка 1: ёмкость 1, место есть, копий 0
вставка 2: полно → удвоение до 2, копий 1
вставка 3: полно → удвоение до 4, копий 2
вставка 4: место есть, копий 0
вставка 5: полно → удвоение до 8, копий 4
вставки 6,7,8: место есть, копий 0
всего копий: 1 + 2 + 4 = 7  (< 2·8 = 16)

Восемь вставок стоили 8 размещений плюс 7 копий - 15 действий, меньше 2 на вставку. Копирования пришлись только на удвоения (размеры 1, 2, 4) и сложились в геометрический ряд 1 + 2 + 4 = 7. Восьмёрка - ровно степень двойки, поэтому восьмая вставка попадает в аккурат заполненный буфер и удвоения не требует; при n = 9 добавилось бы удвоение до 16 с копированием восьми, и сумма стала бы 1 + 2 + 4 + 8 = 15 < 2·9 - тот же порядок Θ(n). Будь массив вдесятеро длиннее, копий было бы < 2n, и средняя так и осталась бы около двух - вот что значит O(1) амортизированно.

Что ломается без этого

Две ошибки. Взять максимум по одной операции и объявить его ценой каждой: у вставки это дало бы Θ(n) на вставку и Θ(n²) на серию - завышение тем сильнее, чем длиннее серия (в разы), потому что дорогие вставки посчитаны так, будто они каждая. И спутать с средним случаем: сказать «в среднем O(1), но на плохом входе O(n) за вставку» - амортизация как раз про то, что плохой серии, дорогой в среднем, НЕ существует.

Зачем это в работе

Динамические массивы, хеш-таблицы с рехешем, StringBuilder - всё это внутри делает редкие дорогие перестройки, и без амортизации их пришлось бы считать дорогими всегда. Амортизация объясняет, почему list.append в Python считают O(1), хотя иногда он копирует весь список: по любой серии добавлений средняя цена константна. Это не поблажка, а строгая гарантия, на которую опираются библиотеки.

Теперь сам

n операций серии: цена i-й операции равна i, если i - точная степень двойки, и 1 иначе. Найди амортизированную цену агрегатным методом.