Метод потенциалов (амортизационный анализ)

Метод потенциалов — один из методов амортизационного анализа, позволяющий «сгладить» влияние дорогих, но редких операций на суммарную вычислительную сложность алгоритма.

Определения Править

В методе потенциалов вводится функция $\mathrm{\Phi <!--\; \Phi \; -->}$$\Phi$ , связывающая состояние структуры данных с некоторым неотрицательным числом. Смысл данной функции заключается в том, что если $S$$S$  — текущее состояние структуры, то $\mathrm{\Phi <!--\; \Phi \; -->}(S)$$\Phi (S)$  — это величина, характеризующая объём работы «дорогих» операций, который уже был «оплачен» более дешёвыми операциями, но не был произведён. Таким образом, $\mathrm{\Phi <!--\; \Phi \; -->}(S)$$\Phi (S)$  может рассматриваться как аналог потенциальной энергии, ассоциированной с данным состоянием. Изначально значение потенциальное функции обычно полагается равным нулю.

Пусть $o$$o$  — некоторая отдельная операция из серии, $S_{before}$$S_{before}$  — состояние структуры до этой операции, а $S_{after}$$S_{after}$  — после неё. Тогда амортизированная сложность операции $o$$o$  равна

$T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(o)=T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o)+\mathrm{\Phi <!--\; \Phi \; -->}(S_{\mathrm{a}\mathrm{f}\mathrm{t}\mathrm{e}\mathrm{r}})-<!--\; -\; -->\mathrm{\Phi <!--\; \Phi \; -->}(S_{\mathrm{b}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}}).$$T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} }).$ 

Соотношения между амортизированной и реальной стоимостью Править

Суммарная амортизированная стоимость последовательности операций является валидной оценкой сверху для реальной стоимости этой последовательности операций.

Для последовательности операций $O=o_1,o_2,\dots <!--\; \dots \; -->,o_n$$O=o_{1},o_{2},\dots ,o_{n}$ , можно определить:

• Суммарное амортизированное время: $T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)=\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{T}_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(o_i),$$T_{\mathrm {amortized} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortized} }(o_{i}),$ 
• Суммарное реальное время: $T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)=\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}{T}_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o_i).$$T_{\mathrm {actual} }(O)=\sum _{i=0}^{n}T_{\mathrm {actual} }(o_{i}).$ 

В таких обозначениях:

$T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\left(T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(o_i)+\mathrm{\Phi <!--\; \Phi \; -->}(S_i)-<!--\; -\; -->\mathrm{\Phi <!--\; \Phi \; -->}(S_{i-<!--\; -\; -->1})\right)=T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)+\mathrm{\Phi <!--\; \Phi \; -->}(S_n)-<!--\; -\; -->\mathrm{\Phi <!--\; \Phi \; -->}(S_0),$$T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+\Phi (S_{i})-\Phi (S_{i-1})\right)=T_{\mathrm {actual} }(O)+\Phi (S_{n})-\Phi (S_{0}),$ 

Таким образом, последовательность значений потенциальной функции образует телескопическую сумму, в которой последовательные начальные и конечные значения потенциальной функции сокращаются друг с другом.

Из того, что $\mathrm{\Phi <!--\; \Phi \; -->}(S_0)=0$$\Phi (S_{0})=0$  и $\mathrm{\Phi <!--\; \Phi \; -->}(S_n)\ge <!--\; \ge \; -->0$$\Phi (S_{n})\geq 0$  следует неравенство $T_{\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{a}\mathrm{l}}(O)\le <!--\; \le \; -->T_{\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}}(O)$$T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)$ , как и было сказано ранее.

Примеры Править

Стек с массовыми удалениями Править

Можно рассмотреть вариант стека, поддерживающий следующие операции:

• initialize — создать пустой стек.
• push — добавить единственный элемент на верхушку стека, увеличив его размер на $1$$1$ .
• pop(k) — убрать $k$$k$  элементов с верхушки стека, где $k$$k$  не превосходит текущий размер стека.

Одна операция pop(k) требует $O(k)$$O(k)$  времени, совокупное же время работы может быть проанализировано с помощью следующей потенциальной функции $\mathrm{\Phi <!--\; \Phi \; -->}(S)$$\Phi (S)$ , равной числу элементов в стеке $S$$S$ . Данная величина всегда неотрицательна, при этом операция push работает за константу и увеличивает $\mathrm{\Phi <!--\; \Phi \; -->}$$\Phi$  на единицу, а операция pop работает за $O(k)$$O(k)$ , но также уменьшает потенциальную функцию на $k$$k$ , поэтому её амортизированное время также константно. Из этого следует, что суммарное время исполнения любой последовательности из $m$$m$  операций равно $O(m)$$O(m)$  в худшем случае.

Двоичный счётчик Править

Другим примером является счётчик, реализованный в виде двоичного числа, поддерживающего такие операции:

• initialize -- создать счётчик со значением $0$$0$ .
• inc — увеличить значение счётчика на $1$$1$ .

Чтобы показать, что амортизированная стоимость inc равна $O(1)$$O(1)$ , следует рассмотреть потенциальную функцию, равную числу бит счётчика, равных $1$$1$  (вес Хемминга^[en] счётчика). Как и требуется, такая функция всегда неотрицательна и изначально равна $0$$0$ . Операция inc сперва инвертирует младший значимый бит счётчика, а затем, если он был равен $1$$1$ , повторяет то же самое со следующим битом, пока не наткнётся на $0$$0$ . Если до этого в конце битовой записи счётчика было $k$$k$  единичных битов, потребуется инвертировать $k+1$$k+1$  бит, затрачивая $k+1$$k+1$  единиц реального времени и уменьшая потенциал на $k-<!--\; -\; -->1$$k-1$ . Таким образом, амортизированная стоимость операции inc равна $2$$2$  и, как следствие, время исполнения $m$$m$  операций inc равно $O(m)$$O(m)$ .

Применения Править

Метод потенциалов обычно используется для анализа фибоначчиевых куч, в которых извлечение элемента требует амортизированно логарифмического времени, а все остальные операции занимают амортизированно константное время. Также с его помощью можно показать, что splay-дерево обладает логарифмической амортизированной стоимостью операций.