Конспект: амортизированный анализ

Понятия

Амортизированная цена - средняя цена операции по СЕРИИ из n операций в худшем случае, без вероятности. Гарантия по любой серии, даже худшей (этим отличается от среднего случая - ожидания по случайным входам).

Агрегатный метод - посчитать общую цену серии T(n) и поделить на n: амортизированная цена = T(n)/n.

Метод предоплаты (учётный) - назначить операции цену ĉ; переплата копится кредитом, дорогие операции платят из него; кредит всегда ≥ 0, тогда Σĉ ≥ Σc.

Метод потенциалов - функция Φ(D) ≥ 0 от состояния, Φ(D₀) = 0; амортизиро‐ ванная цена ĉ = c + Φ(после) − Φ(до). При суммировании средние Φ телескопируются: Σĉ = Σc + Φ(D_n) ≥ Σc.

Динамический массив - буфер, который удваивается при заполнении и копирует старое. num занято, size ёмкость, коэффициент заполнения num/size.

Что унести

Три метода дают одну оценку. Агрегатный - грубее и сразу на всю серию; предоплата и потенциал считают цену каждой операции и не требуют знать серию наперёд. Кредит предоплаты и значение Φ - одно и то же число: накопленный про запас ресурс.

Вставка в динамический массив - O(1) амортизированно. Потенциал Φ = 2·num − size («заполнение сверх половины»): обычная вставка поднимает Φ на 2, цена 1 + 2 = 3; вставка с удвоением (num = size = s) копирует s, но Φ падает с s до 2, цена (s+1) + 2 − s = 3. Запас копится при заполнении и тратится на удвоении.

С удалениями нужен ЗАЗОР между порогами: удваивать при заполнении 1, ужимать вдвое ниже 1/4. Сжатие при 1/2 даёт качели у границы - Θ(n) на операцию. Потенциал из двух ветвей: 2·num − size выше половины, size/2 − num ниже; обе равны нулю при α = 1/2.

Удвоение принципиально. Рост на постоянные +c даёт n/c перестроек и c + 2c + ... = Θ(n²) копирований (арифметический ряд) - вставка Θ(n). Удвоение даёт 1 + 2 + 4 + ... + n < 2n = Θ(n) (геометрический ряд) - вставка O(1). Тот же геометрический ряд стоит за агрегатным доказательством и за двоичным счётчиком (O(1) на увеличение, не Θ(log n)).

Стек с multipop - канонический пример: Φ = высота стека, push стоит 2, pop и multipop(k) - 0 (гасятся падением Φ). Дорогой multipop бесплатен амортизированно, потому что его заранее оплатили push-и.

Это внутренность list/ArrayList/vector: append - O(1) амортизированно, а склейка строки в цикле (s = s + c) - Θ(n²), потому что строку нельзя дописать на месте, её копируют целиком.

Ловушки джокера

Спутал амортизацию со средним случаем. Амортизация не знает вероятностей: гарантия по любой серии, а не по удаче. «В среднем O(1), но на плохом входе O(n)» - это НЕ амортизация.

Взял максимум по одной операции. Объявить вставку Θ(n) (по удвоению) и серию Θ(n²) - завышение: дорогие удвоения редки, серия Θ(n).

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

Взял Φ с отрицательными значениями или ненулевым стартом. Тогда Φ(конец) − Φ(старт) бывает отрицательным, Σĉ < Σc, оценка перестаёт быть верхней.

Сжал буфер на том же пороге, на котором расширял. Массив у границы перестраивается на каждой второй операции; порог сжатия - 1/4, а не 1/2.

Нарастил буфер на константу ради памяти. Сэкономишь память, но вставка станет Θ(n) амортизированно, а построение массива - Θ(n²).

Проверь себя

Чем амортизированная цена отличается от среднего случая?

Как считают амортизированную цену тремя методами (агрегатным, предоплатой, потенциалом)?

Зачем в методе потенциалов нужны Φ ≥ 0 и Φ(D₀) = 0?

Почему вставка в динамический массив O(1) амортизированно и при чём тут Φ = 2·num − size?

Почему буфер удваивают, а не наращивают на константу?

Почему list.append считают O(1), а склейку строки в цикле - Θ(n²)?

Почему буфер ужимают при заполнении ниже 1/4, а не ниже 1/2?