Введение
Нередко при работе со структурами данных мы сталкиваемся с частыми последовательными вызовами операций. Можно проследить, что фактическая временная сложность операции зависит от текущего состояния структуры данных, то есть вызовы в разные моменты времени даже одной и той же операции могут сильно отличаться по времени. Говорить о временной сложности в худшем случае при этом может быть очень грустно: оценка может получиться слишком грубой в том смысле, что реально такая сложность достигается не так часто.
Например, вы хотите купить автомобиль за 1 200 000 ₽. Предположим, что ваша зарплата составляет 150 000 ₽, и вы планируете осуществить покупку за один год. Попробуем оценить сверху ту сумму, которую мы будем перечислять ежемесячно из нашей зарплаты на отдельный счет «автомобиль мечты». Можно не заниматься никакими разделениями средств на своих картах и через одиннадцать месяцев скинуть на счет «автомобиль мечты» 1 200 000 ₽. В этом случае получается, что наши отчисления в худшем случае составили 1 200 000 ₽. Если так оценить вообще все наши ежемесячные отчисления (при том, что большинство из них составили 0 ₽), то может показаться, что нашей зарплаты никогда не хватит на покупку автомобиля. Но это не совсем так. Оценка получилась чересчур грубой, хоть и верной.
Можно пойти и по другому пути. Будем отчислять каждый месяц по 100 000 ₽ на счет «автомобиль мечты». Тогда к последнему месяцу мы наберем необходимую сумму и купим автомобиль, имея зарплату в 150 000 ₽. Видно, что оценка 100 000 ₽/мес. выглядит куда более реалистичной, так как она уже учитывает в себе тот факт того, что автомобиль покупается в течение года.
Если убрать из виду отдельные счета, и вообще все конкретное, что мы делали на картах с деньгами, очевидно одно: суммарно за год мы все равно заплатим 1 200 000 ₽. Однако оценка, что мы каждый месяц делаем выплату не более 100 000 ₽ выглядит куда более информативно, чем то, что в худшем случае мы потратим 1 200 000 ₽.
Амортизационный анализ как раз и основан на похожих идеях. Он дает возможность вычислять и доказывать более гибкие оценки на суммарную сложность цепочки операций.
Вычисление средней сложности
Везде далее, в качестве примера, будет изучена следующая ситуация. Рассмотрим пустой вектор целых чисел std::vector<int>, над которым последовательно выполнили цепочку из $m$ операций push_back(x).
Известно, что некоторые из этих операций требуют реаллокации: создание нового участка памяти вдвое большего размера, и последовательное копирование элементов старого вектора в новый. Потому в худшем случае вставка в конец вектора оценивается как $\mathcal{O}(n)$. Представьте, если бы вам в документации заявили такую сложность.
Совершенно ясно, что большая часть наших push_back(x) из цепочки не делают никаких реаллокаций: они просто записывают элемент в память. Быть может, будет уместна средняя оценка на время работы?
Важно отметить, что средняя сложность одна и вычисляется для совершенно конкретной цепочки операций.
В нашем случае $a_i=$push_back. Понятно, что реаллокаций будут требовать только те вызовы операции push_back, при которых количество элементов вектора представляет степень двойки, а это ровно те $a_i$, для которых $i-1$ является степеню двойки. Получаем
Следуя недавно сформулированному определению, вычислим среднюю сложность:
\[c_{\text{avg}} = \dfrac{\displaystyle\sum_{i=1}^m c_i}{m} = \dfrac{\displaystyle\sum_{i=1}^m 1 + \sum_{j=1}^{\lfloor \log_2{(m-1)} \rfloor} 2^j}{m} = \dfrac{m+\mathcal{O}(2^{\lfloor\log_2{(m-1)}\rfloor})}{m} = \dfrac{\mathcal{O}(m)}{m} = \mathcal{O}(1).\]Второе равенство следует из верности оценки сверху возрастающей геометрической прогрессии через последний самый большой член.
Таким образом заключаем, что средняя сложность по цепочке push_back составляет $\mathcal{O}(1)$, что гораздо более верно оценивает эту операцию в целом. Иными словами, обычно push_back очень быстрая операция.
Банковский метод
Даже в случае с операцией push_back пришлось сделать немало математических вычислений, чтобы получить точное значение $c_{\text{avg}}$. В более сложных структурах данных подобные вычисление могут быть непосильно трудными. Для решения этой проблемы Роберт Тарьян и пишет работу по амортизационному анализу, предлагая инструмент, позволяющий оценивать сверху среднюю сложность. Как мы знаем, реальные сложности операций в цепочке $c_i$ могут очень сильно колебаться, и если найти способ, как оценить все эти колебания, то можно будет говорить и об оценке общей суммарной сложности.
Изучим банковский метод. Предположим, что компьютер очень любит рубли и что за 1 ₽ он готов выполнить константное количество атомарных операций. (Почем сейчас рубль? В разных анализах можно уточнить, сколько именно операций, если это нужно.) Также представим себе, что у нас есть отдельный изначально пустой мешок, куда можно складывать и копить рубли. За каждую операцию мы будем начислять себе на руки определенное количество рублей - зарплату.
Также у операции есть ее реальная временная сложность $c_i$. Столько рублей мы будем вынуждены платить за ее выполнение. Наша цель показать, что все операции цепочки могут быть выполнены за указанные учетные стоимости $c’_i$. Если нам дали больше денег, чем операция стоит на самом деле, то мы имеем возможность расплатиться за нее, а затем сложить оставшуюся валюту в мешок (либо вообще выкинуть :)). Если учетной стоимости недостаточно, чтобы выполнить некоторую дорогую операцию, то мы вынужденны пользоваться накоплениями и достать какое-то количество нехватающих денег из мешка. Необходимо показать, что денег в мешке хватает всегда, иначе анализ не сойдется. В этом методе нельзя брать кредиты, то есть просить еще денег из уже пустого мешка.
Понятно, что если мы смогли доказать, что денег для оплаты цепочки операций достаточно, то суммарная фактическая временная сложность всех операций будет оценена сверху суммой всех амортизированный сложностей.
На практике накопления удобно складывать не в мешок, а размещать прямо внутри структуры данных, на ее элементах, узлах. Здесь важно сделать замечание, что все эти деньги — наша выдумка для науки, в коде никаких рублей нет и хранить их не нужно.
Проведем анализ той же цепочки push_back банковским методом. Так как мы целимся в амортизационную оценку $\mathcal{O}(1)$, то нам необходимо просить каждый раз одинаковое фиксированное количество рублей. Попросим за каждый push_back по 4 ₽.
Чтобы показать, что при любом раскладе у нас хватит денег в запасе, необходимо сформулировать и доказать инвариант раскладки денег по структуре данных. Заметим, что следующие неравенства верны для любого момента времени:
\[\dfrac{\texttt{capacity}}{2} \leqslant \texttt{size} \leqslant \texttt{capacity}.\]Они следуют напрямую из устройства реаллокаций в процессе push_back: вектор действительно всегда заполнен хотя бы наполовину. Утвердим следующий инвариант: в правой половине вектора (от $1/2\, \texttt{capacity}$ до $\texttt{capacity}$) над каждым элементом лежит по 2 ₽. Проверим теперь, на каждый ли push_back нам хватит этих денег и сохраняется ли этот инвариант. Для этого рассмотрим два случая.
Пусть в процессе push_back реаллокация не потребовалась. Тогда нам выдают 4 ₽, 1 ₽ мы тратим на непосредственное присваивание элемента в память вектора, 2 ₽ положим над этим элементом, а 1 ₽ выкинем. Инвариант не нарушен, денег хватило.
Теперь случай сложнее: случилась реаллокация. Нам снова дают те же самые 4 ₽. В этой ситуации 1 ₽ мы потратим на выделение новой памяти под вектор. Каждый элемент старой правой половины будет оплачивать по 1 ₽ копирование соответствующего ему элемента левой половины, и по 1 ₽ за копирование себя в новый вектор. Заметим, что все скопированные элементы теперь лежат в левой половине нового вектора и по нашему инварианту мы не должны беспокоиться о деньгах над ними. Добавим теперь элемент в новый вектор, потратив на это 1 ₽ из зарплаты. Остались 2 ₽, которые мы кладем над этим новым элементом. Так как это единственный элемент в новой правой половине, инвариант не нарушен. Денег хватило.
Таким образом у нас сошелся анализ банковским методом операции push_back. Его амортизированная стоимость получилась равна 4, что составляет $\mathcal{O}(1)$.
Сформулируем банковский метод по шагам:
- Ввести «валюту». Сформулировать какие операции и сколько готова выполнять машина за 1 единицу валюты.
- Назначить амортизационные сложности каждой операции - попросить зарплату за каждую операцию.
- Сформулировать инвариант: где и сколько гарантированно лежат средства в любой момент времени.
- Для каждой операции четко прописать, какие деньги и куда тратить, как перекладывать. Показать, что инвариант не нарушается ни при каких условиях и что денег всегда хватает.
Физический метод
Существует в каком-то смысле более математически строгий способ вывода амортизационных сложностей.
Рассмотрим некоторую структуру данных $\mathcal D$. Пусть выполняется конечная цепочка из $m$ операций над ней $a_i$, причем, в процессе применения этих операций, будут изменяться внутренние состояния $S_i\in \texttt{States}$ структуры $\mathcal D$. В начале структура данных находится в стартовом состоянии $S_0$.
\[\mathcal{D}\colon\, S_0 \xrightarrow[c_1]{a_1} S_1 \xrightarrow[c_2]{a_2} S_2 \rightarrow \ldots \xrightarrow[c_m]{a_m} S_{m}\]Пусть все операции $a_i$ имеют настоящую сложность $c_i$ (в худшем случае). Определим функцию потенциала на множестве состояний:
\[\varphi\colon\,\texttt{States}\to\mathbb{Z}_{\geqslant 0},\]причем потребуем обязательно, чтобы $\varphi(S_0) = 0$, то есть потенциал структуры данных $\mathcal{D}$ изначально равен нулю. Обратите внимание, область значений функции $\varphi$ это целые неотрицательные числа.
Именно из-за наличия во всей этой терминологии «потенциала» структуры данных метод и называется физическим. Видно, что амортизационная сложность операции на самом деле равняется исходной сложности с поправкой на разность потенциалов, а именно из потенциала состояния, в которое перешла структура данных после выполнения операции, необходимо вычесть потенциал состояния, которое было до выполнения.
Вспомним, что цель амортизированных оценок — суммарно накрыть сверху реальную суммарную сложность всех операций. Проверим, так ли это на самом деле, сложив все амортизированные стоимости $c’_i$ по определению физического метода.
\[\begin{aligned} \sum_{i=1}^m c'_i &= c_1 + \varphi(S_1) - \varphi(S_0) \\ &+c_2 + \varphi(S_2) - \varphi(S_1) \\ &+ \quad\cdots \\ &+c_n+ \varphi(S_n) - \varphi(S_{n-1}). \end{aligned}\]Видим, что большинство слагаемых, кроме $c_i$ и самых крайних $\varphi(S_0)$ и $\varphi(S_n)$, взаимно уничтожаются. Получаем,
\[\sum_{i=1}^m c'_i = \sum_{i=1}^m c_i + \varphi(S_n) - \varphi(S_0).\]Откуда
\[\sum_{i=1}^m c_i = \sum_{i=1}^m c'_i + \varphi(S_0) - \varphi(S_n).\]Так как $\varphi(S_0) = 0$ и $\varphi(S_i) \geqslant 0$ (теперь понятно, зачем было это требовать в определении функции потенциала), получаем оценку
\[\sum_{i=1}^m c_i \leqslant \sum_{i=1}^m c'_i.\]Если мы хотим показать, например, что амортизационная сложность для операций составляет константу $\mathcal{O}(1)$, то нам нужно подобрать функцию потенциала $\varphi$ таким образом, чтобы существовало такое достаточно большое фиксированное число $T$ и $\forall\,i$ было верно $c’_i \leqslant T$.
Тогда из неравенства выше получается
\[\sum_{i=1}^m c_i \leqslant \sum_{i=1}^m c'_i \leqslant mT \Rightarrow \frac{\sum_{i=1}^m c_i}{m} \leqslant T.\]Действительно, амортизационная сложность $T$ будет давать оценку сверху на среднюю сложность по цепочке операций.
Таким образом, на практике вся наука будет работать, если только суметь грамотно подобрать неотрицательную функцию $\varphi$ на множестве состояний структуры $\mathcal{D}$, а затем вычислить $c’$ для нужной операции и показать, что получается, что нужно.
Интуитивно можно воспринимать потенциал состояния структуры данных как ее некоторый «заряд». Действительно, если мы совершаем быструю операцию $a_i$ с маленьким $c_i$, то потенциал $\varphi(S_i)$ должен вырасти, и обратно, если операция сложная и долгая, то структура данных как бы «разряжается», и потенциал падает, тратя «накопленную энергию» за счет быстрых операций. Получается, если быстрых операций достаточно много, и мы накопим хороший потенциал, то у нас получится «сгладить» прыжок по реальной сложности $c_i$ у дорогой операции.
Применим физический метод к анализу цепочки push_back над изначально пустым вектором целых чисел. Обычно, в качестве состояния выбирают конкретные важные для анализа структуры данных параметры. В нашем случае определим состояние $S=(\texttt{size},\,\texttt{capacity})$ как пару параметров вектора. Функцию потенциалов выберем следующим образом
Заметим, что в любой момент времени для вектора верно $\texttt{size}_i \geqslant \frac{\texttt{capacity}_i}{2}$. Таким образом $\varphi(S_i)\geqslant 0$. Также $\varphi(S_0) = 2\cdot 0 - 0 = 0$. Следовательно, функция $\varphi$ удовлетворяет требованиям функции потенциала.
Вычислим теперь амортизационную сложность операции push_back. По определению получаем
Здесь тоже приходится разбирать два случая. Предположим, что реаллокация не потребовалась. В таком случае $c_i=1$, так как мы просто заносим новый элемент в ячейку памяти, $\texttt{size}_i = \texttt{size}_{i-1} + 1$, при этом $\texttt{capacity}_i=\texttt{capacity}_{i-1}$, так как эта характеристика без реаллокаций принципиально не меняется. Подставляя все это выше, получим
\[c'_i = 1 + 2\times(\texttt{size}_{i-1} + 1) - \texttt{capacity}_{i-1} - 2\times\texttt{size}_{i-1} + \texttt{capacity}_{i-1} = 3.\]Теперь рассмотрим случай, когда реаллокация была сделана. Для простоты обозначений положим, что $\texttt{size}_{i-1} = \texttt{capacity}_{i-1} = k$. Тогда $c_i = k + 1$, так как нам необходимо сначала скопировать $k$ элементов вектора, а затем приписать туда новый. Далее $\texttt{size}_i = k + 1$, а $\texttt{capacity}_i=2k$. Получаем
\[c'_i = k + 1 + 2(k + 1) - 2k - 2k + k = 3.\]Таким образом, физическим методом было показано, что амортизационная сложность операции push_back составляет $\mathcal{O}(1)$.
Проверьте, сойдется ли амортизационный анализ для той же цепочки push_back, если использовать функцию потенциала $\varphi(S) = 3\times \texttt{size} - \texttt{capacity}$.
Да, такая формула будет работать. Сделаем те же подстановки для случая без реаллокации $\varphi(S) = 1 + 3(\texttt{size}_{i-1}+1) - \texttt{capacity}_{i-1} - 3\cdot \texttt{size}_{i-1} + \texttt{capacity}_{i-1}=4=\mathcal{O}(1)$. Для случая с реаллокацией используем те же обозначения: $\varphi(S)=k + 1 + 3(k+1) - 2k - 3k + k=4=\mathcal{O}(1)$. Нетрудно догадаться, что для расширения вектора в 2 раза будет годиться любая формула вида $\varphi(S)=\lambda\texttt{size} - \texttt{capacity},\,\lambda\geqslant2$.
