Амортизационный анализ

Амортизационный анализ — это метод оценки вычислительной сложности алгоритмов, при котором средняя стоимость выполнения последовательности операций вычисляется не как среднее арифметическое, а как верхняя граница, гарантированная для всей последовательности целиком. В отличие от обычного анализа худшего случая, амортизационный анализ учитывает, что дорогие операции могут происходить редко, а их стоимость «распределяется» (амортизируется) на множество дешёвых операций, выполняемых до или после. Результатом является амортизированная стоимость одной операции — постоянная или логарифмическая величина, которая не зависит от длины последовательности и не требует вероятностных допущений (в отличие от среднего случая). Амортизационный анализ применяется для оценки структур данных, в которых отдельные операции могут быть дорогими, но их частота мала.

История

Метод амортизационного анализа был впервые формализован в 1985 году американскими учёными Робертом Тарьяном и Джоном Хопкрофтом в контексте анализа структуры данных «disjoint-set forest» (лес непересекающихся множеств). Тарьян показал, что последовательность из \(m\) операций над такой структурой выполняется за время \(O(m \alpha(m, n))\), где \(\alpha\) — обратная функция Аккермана, что является амортизированной оценкой. Позднее метод был распространён на другие динамические структуры: хеш-таблицы с перехешированием, двоичные кучи, очереди с приоритетами (фибоначчиевы кучи) и динамические массивы. В 1986 году Тарьян опубликовал монографию «Amortized Computational Complexity», где закрепил терминологию и основные техники.

Основные понятия

Амортизационный анализ рассматривает последовательность из \(n\) операций, каждая из которых имеет фактическую стоимость \(c_i\). Амортизированная стоимость \(\hat{c}_i\) определяется так, чтобы для любой последовательности выполнялось неравенство:

\[ \sum_{i=1}^{n} \hat{c}_i \ge \sum_{i=1}^{n} c_i \]

То есть сумма амортизированных стоимостей всегда не меньше суммы фактических. Амортизированная стоимость может быть больше фактической для дешёвых операций (создавая «резерв»), и меньше — для дорогих (используя накопленный резерв). Ключевое свойство: если амортизированная стоимость каждой операции ограничена константой \(O(1)\), то вся последовательность из \(n\) операций выполняется за \(O(n)\).

Методы амортизационного анализа

Существуют три основных метода получения амортизированных оценок: метод группировки (или метод учёта), метод потенциалов и метод бухгалтерского учёта.

Метод группировки (метод учёта)

В этом методе каждая операция «платит» некоторую фиксированную сумму — амортизированную стоимость. Часть этой суммы тратится на выполнение самой операции, а остаток откладывается в «кредит» (виртуальный счёт). Когда происходит дорогая операция, она использует накопленный кредит. Необходимо гарантировать, что кредит никогда не становится отрицательным. Амортизированная стоимость выбирается так, чтобы для любой последовательности суммарный кредит оставался неотрицательным.

Пример: динамический массив (например, std::vector в C++). При добавлении элемента, если массив заполнен, выделяется новый массив вдвое большего размера, и все элементы копируются. Фактическая стоимость вставки в худшем случае — \(O(n)\). Амортизированная стоимость вставки — \(O(1)\). В методе группировки каждая вставка «платит» 3 единицы: 1 — на запись нового элемента, 2 — на будущее копирование (при переполнении). После \(n\) вставок накоплено \(2n\) кредита, а на копирование \(n\) элементов тратится \(n\) единиц, что не превышает кредита.

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

Метод потенциалов использует функцию потенциала \(\Phi(D)\), которая отображает состояние структуры данных \(D\) в неотрицательное число. Амортизированная стоимость \(i\)-й операции определяется как:

\[ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \]

где \(D_{i-1}\) — состояние до операции, \(D_i\) — после. Сумма амортизированных стоимостей равна сумме фактических плюс изменение потенциала:

\[ \sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0) \]

Если \(\Phi(D_n) \ge \Phi(D_0)\), то сумма амортизированных стоимостей не меньше суммы фактических. Потенциал выбирается так, чтобы дорогие операции уменьшали потенциал, а дешёвые — увеличивали.

Пример: для динамического массива потенциал можно определить как \(\Phi = 2 \cdot \text{size} - \text{capacity}\), где size — количество элементов, capacity — ёмкость. При вставке без переполнения потенциал увеличивается на 2, амортизированная стоимость — 3. При вставке с переполнением (копирование \(n\) элементов) потенциал падает почти до нуля, амортизированная стоимость — \(n + (0 - 2n) = -n\)? Нет, это даёт 3, если правильно подобрать. На практике для динамического массива потенциал \(\Phi = 2 \cdot \text{size} - \text{capacity}\) даёт амортизированную стоимость 3.

Метод бухгалтерского учёта

Этот метод похож на метод группировки, но использует явную «банковскую» метафору. Каждой операции назначается амортизированная стоимость. Часть её тратится на выполнение, остаток кладётся на счёт. Дорогие операции снимают со счёта. Необходимо, чтобы баланс счёта никогда не был отрицательным. Амортизированная стоимость — это максимальная сумма, которую можно «заплатить» за операцию, сохраняя неотрицательность баланса.

Примеры применения

Динамический массив (Dynamic Array)

Динамический массив (например, ArrayList в Java или vector в C++) поддерживает операции вставки в конец. При переполнении массив увеличивается в 2 раза (или в 1.5 раза в некоторых реализациях). Амортизированная стоимость вставки — \(O(1)\). Доказательство методом потенциалов: потенциал \(\Phi = 2 \cdot \text{size} - \text{capacity}\). При вставке без переполнения \(\Delta \Phi = 2\), \(\hat{c} = 1 + 2 = 3\). При вставке с переполнением (копирование size элементов) \(\Delta \Phi = 2 \cdot (\text{size}+1) - 2\cdot\text{size} - (\text{capacity} - \text{capacity}) = 2 - (2\cdot\text{size} - \text{capacity}) = 2 - (2\cdot\text{size} - 2\cdot\text{size}) = 2\)? На самом деле, при удвоении capacity становится \(2\cdot\text{size}\), а size увеличивается на 1. Тогда \(\Phi_{\text{new}} = 2(\text{size}+1) - 2\cdot\text{size} = 2\), \(\Phi_{\text{old}} = 2\cdot\text{size} - \text{size} = \text{size}\). Изменение \(\Delta \Phi = 2 - \text{size}\). Амортизированная стоимость: \(\hat{c} = \text{size} + (2 - \text{size}) = 2\). Итого амортизированная стоимость — константа.

Очередь с приоритетами (Фибоначчиева куча)

Фибоначчиева куча — структура данных, поддерживающая операции вставки, слияния, уменьшения ключа и удаления минимума. Амортизированная стоимость вставки и слияния — \(O(1)\), уменьшения ключа — \(O(1)\), удаления минимума — \(O(\log n)\). Доказательство использует метод потенциалов с потенциалом, равным числу деревьев в куче плюс удвоенное число помеченных узлов. Эта структура применяется в алгоритмах Дейкстры и Прима.

Хеш-таблицы с перехешированием

При вставке в хеш-таблицу, если коэффициент заполнения превышает порог, выполняется перехеширование — создание новой таблицы большего размера и перестановка всех элементов. Амортизированная стоимость вставки — \(O(1)\). Анализ аналогичен динамическому массиву.

Лес непересекающихся множеств (Union-Find)

Структура данных для поддержки непересекающихся множеств с операциями find и union. При использовании эвристик сжатия пути и объединения по рангу амортизированная стоимость операций — \(O(\alpha(n))\), где \(\alpha\) — обратная функция Аккермана, которая растёт крайне медленно (для всех практических \(n\) не превышает 5). Доказательство сложное и использует метод потенциалов с потенциалом, зависящим от рангов узлов.

Сравнение с другими видами анализа

• Анализ худшего случая (worst-case analysis) оценивает максимальную стоимость одной операции. Для динамического массива вставка в худшем случае — \(O(n)\), что может быть неприемлемо в системах реального времени.
• Анализ среднего случая (average-case analysis) предполагает вероятностное распределение входных данных. Амортизационный анализ не требует вероятностей — он гарантирует верхнюю границу для любой последовательности.
• Анализ с учётом конкуренции (competitive analysis) используется для онлайн-алгоритмов.

Амортизационный анализ особенно полезен для структур данных, где дорогие операции редки, и их стоимость можно «размазать» по многим дешёвым.

Критика и ограничения

Амортизационный анализ даёт оценку средней стоимости на длинной последовательности, но не гарантирует низкой стоимости отдельной операции. В системах реального времени, где критично время выполнения каждого запроса, амортизированные оценки неприменимы — требуется анализ худшего случая. Кроме того, выбор функции потенциала может быть нетривиальным, и для некоторых структур данных (например, скошенных деревьев) амортизированные оценки сложны в доказательстве.

Интересные факты

• Термин «амортизационный» заимствован из экономики, где амортизация — это распределение стоимости актива на срок его службы.
• Для фибоначчиевой кучи амортизированная стоимость уменьшения ключа — \(O(1)\), что делает её эффективной для алгоритмов, где много таких операций (например, алгоритм Дейкстры).
• Обратная функция Аккермана \(\alpha(n)\) растёт настолько медленно, что для всех практических \(n\) (до \(10^{100}\)) она не превышает 5, поэтому амортизированная стоимость операций Union-Find считается практически константной.

Источники

• Тарьян Р. Э. «Амортизированная вычислительная сложность» (Amortized Computational Complexity, 1986).
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms, 3-е издание, 2009).
• Кнут Д. Э. «Искусство программирования» (The Art of Computer Programming, том 3, 1973).
• Седжвик Р., Уэйн К. «Алгоритмы на Java» (Algorithms, 4-е издание, 2011).