Занятие 10. Амортизационный анализ и динамические структуры

Семинар закрывает два долга: занятие 8 обещало строго доказать «O(1) амортизированно» для push_back, а занятие 2 — объяснить, что вообще значит «дорогая операция, оплаченная дешёвыми». Плюс две классические структуры, где амортизация — суть, а не оптимизация. Замеры реальные (Apple M-серия, clang++ -O2).

Проблема и определение

Худший случай одной операции push_back — $O(n)$: переезд всего массива. Значит ли это, что $n$ операций стоят $O(n^2)$? Нет: дорогие операции редки. Амортизационный анализ узаконивает это рассуждение.

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

Операция имеет амортизированную стоимость $t(n)$, если любая последовательность из $m$ таких операций (из начального состояния) выполняется за время $T(m) \le m \cdot t(n)$.

Ключевое отличие от среднего случая: average case усредняет по случайным входам, амортизация — по операциям худшей серии. Никаких вероятностей: гарантия «$n$ операций ≤ $n \cdot t$» держится для любого злого сценария.

Два метода доказательства: усреднение и банковский.

Метод усреднения

Разминка — двоичный счётчик. Инкремент перещёлкивает хвост единиц: в худшем случае все $k$ бит. Но бит $i$ меняется лишь каждые $2^i$ инкрементов, поэтому $n$ инкрементов стоят

$$T(n) = \sum_{i \ge 0} \frac{n}{2^i} \le 2n \;\Rightarrow\; O(1) \text{ амортизированно.}$$

Вектор. Переезды случаются на размерах $1, 2, 4, \dots$: суммарных копирований $\sum 2^j \le 2n$, плюс $n$ вставок — итого $T(n) \le 3n$. Интуиция занятия 8 стала теоремой; экспериментальная сверка — 21 реаллокация на миллион push_back. Та же геометрическая прогрессия, что в мастер-теореме (занятие 6).

Банковский метод

Назначаем операциям тариф в монетках; реальная работа списывает монетки, переплата копится на элементах структуры. Правило корректности: баланс никогда не уходит в минус — тогда тарифы и есть честные амортизированные оценки.

Тариф push_back — 3 монеты: одна за собственную вставку, одна на свой будущий переезд, одна — за «старый» элемент, чьи монетки сгорели в прошлом переезде. К моменту переполнения на каждом элементе лежит монетка — реаллокация оплачена заранее:

Банковский метод: монетки копятся на элементах и оплачивают переезд

Почему геометрический рост обязателен. Стратегии +1 и +k дают $O(n)$ и $O(n/k)$ на операцию — фиксированного тарифа не хватает. Любой множитель $> 1$ (×1.5, ×2) даёт $O(1)$. Стандарт C++, кстати, требует от vector::push_back именно амортизированное $O(1)$ — теория прописана в тексте стандарта. Обратное сжатие делают при заполнении в четверть (не в половину — иначе «пила» push/pop на границе устраивает переезд каждый раз).

Стек с минимумом за O(1)

Задача: обычный стек плюс min() за $O(1)$. Одна переменная-минимум ломается на pop. Решение — параллельный стек минимумов: рядом с каждым элементом храним минимум «его эпохи».

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class MinStack {
public:
    void push(int x) {
        data_.push_back(x);
        mins_.push_back(mins_.empty() ? x : std::min(x, mins_.back()));
    }
    void pop()  { data_.pop_back(); mins_.pop_back(); }
    int top() const { return data_.back(); }
    int min() const { return mins_.back(); }
private:
    std::vector<int> data_, mins_;
};

Инвариант: mins_[i] = min(data_[0..i]). Push его сохраняет (новый минимум = min(старый, x)), pop снимает обе вершины — соответствие 1:1 не рвётся, значит mins_.back() — всегда минимум стека. Цена — ×2 памяти; оптимизация со стеком «рекордов» — задача со звёздочкой.

Очередь на двух стеках

Очередь на двух стеках: push в in, pop из out, переброс при пустом out

push — всегда в стек in; pop — из стека out, а если он пуст — перелить всё из in (порядок переворачивается, два переворота дают порядок очереди):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Queue {
public:
    void push(int x) { in_.push_back(x); }
    int pop() {
        if (out_.empty())
            while (!in_.empty()) { out_.push_back(in_.back()); in_.pop_back(); }
        int v = out_.back(); out_.pop_back(); return v;
    }
private:
    std::vector<int> in_, out_;
};

Частый вопрос: «а если чередовать — push, push, push, pop, push, pop — не придётся ли после перелива перебрасывать всё обратно в in?» Не придётся: дороги назад из out в in нет вообще. Трасса:

push a   in: [a]        out: []
push b   in: [a b]      out: []
push c   in: [a b c]    out: []
pop      out пуст → перелив → out: [c b a], отдаём a;  out: [c b]
push d   in: [d]        out: [c b]   ← d просто лёг в in, out не тронут
pop      out НЕ пуст → отдаём b;     in: [d]  out: [c]

Это законно благодаря инварианту структуры: в out — старые элементы в готовом к выдаче порядке, в in — новые; каждый элемент in моложе любого элемента out. Очередь читается как «out сверху вниз, затем in снизу вверх»: pop обязан брать вершину out (самый старый), а новый push кладёт элемент в in и инвариант не трогает. Перелив случается только в момент, когда out вычерпан до дна.

Амортизированное O(1)

Жизненный цикл любого элемента — ровно четыре элементарных действия: лёг в in → снят с in → положен в out → снят с out, и перелив для него однократный. Тарифы: push — 3 монеты (одна за укладку в in, две остаются на элементе), pop — 1 монета (за снятие с out). Инвариант банка: на каждом элементе in лежат 2 монеты, на элементах out — ноль; перелив $k$ элементов стоит $2k$ действий и сжигает ровно лежащие $2k$ монет. Отдельный pop бывает за $O(n)$, но любая серия из $n$ операций стоит ≤ $4n$ действий — при любом чередовании.

А вот реализация, которая и впрямь гоняла бы элементы туда-обратно (например, на каждый push возвращала всё из out в in, чтобы очередь жила в одном стеке), ломалась бы ровно как «пила» сжатия при пороге $\text{cap}/2$: чередование у границы — и Θ(n) на каждой операции. Лекарство то же, что и там: конструкция, после дорогого шага оказывающаяся далеко от следующего дорогого шага; здесь это однонаправленный поток in → out.

Амортизация ≠ равномерность

Замер одного push_back из серии в $10^7$:

медиана:            0 нс
99-й процентиль:   42 нс
среднее:           14 нс
максимум:   4 722 958 нс   # 4.7 мс — переезд 8 млн элементов

Средняя цена — копейки, но один push из десяти миллионов стоил в ~300 000 раз дороже типичного. Для систем реального времени (игры, аудио, торговля) такой пик — дёрганый кадр или сорванный дедлайн: там нужны честные worst-case гарантии, а не амортизированные. Лекарства: reserve заранее, инкрементальные структуры, аллокации вне горячего пути. И помните: амортизация размазывает стоимость по операциям одной структуры — усреднять между разными объектами нельзя.

Где амортизация живёт: vector/string (занятия 8–9), rehash хеш-таблиц и union-find (второй семестр), компакция логов и LSM-деревья в базах, сборка мусора поколениями, git gc.

Задачи семинара

  1. Счётчик монетками: докажите $O(1)$ инкремента банковским методом — монетка кладётся на каждую единицу. Кто платит за обнуление хвоста?
  2. MinQueue: очередь с минимумом за $O(1)$ аморт. — два MinStack по схеме in/out; минимум очереди = min двух минимумов. (Это стандартный приём для «минимума в скользящем окне» — встретится на рубежном контроле.)
  3. Ленивая очередь: один вектор + индекс головы; физическая чистка — когда голова дошла до половины. Докажите $O(1)$ аморт.

Домашнее задание (сдача через Git)

  1. MinStack и MinQueue + стресс-тест против наивного $O(n)$-минимума.
  2. Письменное доказательство $O(1)$ для очереди на двух стеках банковским методом.
  3. Ленивая очередь: код + анализ.
  4. * MinStack с $O(1)$ дополнительной памяти на неубывающих участках (стек «рекордов» со счётчиками).