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

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

Определения

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

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

T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} }).

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

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

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

Суммарное амортизированное время: $T_{\mathrm {amortized} }(O)=\sum _{i=0}^{n}T_{\mathrm {amortized} }(o_{i}),$
Суммарное реальное время: $T_{\mathrm {actual} }(O)=\sum _{i=0}^{n}T_{\mathrm {actual} }(o_{i}).$

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

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}),

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

Из того, что $\Phi (S_{0})=0$ и $\Phi (S_{n})\geq 0$ следует неравенство $T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)$ , как и было сказано ранее.

Примеры

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

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

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

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

Двоичный счётчик

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

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

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

Применения

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

Примечания

Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Amortization Techniques, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, с. 36–38.
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 18.3 метод потенциалов // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 412—416. — ISBN 5-8459-0857-4.
Cormen et al., Chapter 20, «Fibonacci Heaps», pp. 476—497.
Goodrich and Tamassia, Section 3.4, «Splay Trees», pp. 185—194.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[gt-ad-1] Goodrich, Michael T. & Tamassia, Roberto (2002), 1.5.1 Amortization Techniques, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, с. 36–38.

[clrs-2] Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 18.3 метод потенциалов // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 412—416. — ISBN 5-8459-0857-4.

[3] Cormen et al., Chapter 20, «Fibonacci Heaps», pp. 476—497.

[4] Goodrich and Tamassia, Section 3.4, «Splay Trees», pp. 185—194.