Возможный метод

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

Определение амортизированного времени

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

Пусть o — любая отдельная операция в последовательности операций над некоторой структурой данных, где S _перед обозначением состояния структуры данных до операции o, а S _после обозначения ее состояния после операции o завершения . После выбора Φ амортизированное время операции o определяется как

$T_{\mathrm {amortized} }(o)=T_{\mathrm {actual} }(o)+C\cdot (\Phi (S_{\mathrm {after} })-\Phi (S_{\mathrm {before} })),$

где C — неотрицательная константа пропорциональности (в единицах времени), которая должна оставаться фиксированной на протяжении всего анализа.То есть амортизированное время определяется как фактическое время, затраченное на операцию плюс C , умноженное на разницу потенциалов, вызванную этой операцией.

При изучении асимптотической сложности вычислений с использованием обозначения большого O постоянные факторы не имеют значения, поэтому константа C обычно опускается.

Связь между амортизированным и фактическим временем

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

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

• Общее амортизированное время: $T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}T_{\mathrm {amortized} }(o_{i}),$
• Общее фактическое время: $T_{\mathrm {actual} }(O)=\sum _{i=1}^{n}T_{\mathrm {actual} }(o_{i}).$

Затем:

$T_{\mathrm {amortized} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {actual} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {actual} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),$

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

$T_{\mathrm {actual} }(O)=T_{\mathrm {amortized} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).$

С $\Phi (S_{0})=0$ и $\Phi (S_{n})\geq 0$, $T_{\mathrm {actual} }(O)\leq T_{\mathrm {amortized} }(O)$, поэтому амортизированное время можно использовать для обеспечения точной верхней границы фактического времени последовательности операций, даже если амортизированное время для отдельной операции может сильно отличаться от ее фактического времени.

Амортизированный анализ исходных данных для наихудшего случая

Обычно амортизированный анализ используется в сочетании с предположением о наихудшем случае относительно входной последовательности. При этом предположении, если X — это тип операции, которая может выполняться структурой данных, а n — целое число, определяющее размер данной структуры данных (например, количество содержащихся в ней элементов), то амортизированное время для операций типа X определяется как максимальное среди всех возможных последовательностей операций над структурами данных размера n и всех операций o _i типа X внутри последовательности амортизированное время для операции o _i .

Согласно этому определению время выполнения последовательности операций можно оценить путем умножения амортизированного времени для каждого типа операций в последовательности на количество операций этого типа.

Примеры

Динамический массив

Динамический массив — это структура данных для поддержания массива элементов, обеспечивающая как произвольный доступ к позициям внутри массива, так и возможность увеличения размера массива на единицу. Он доступен в Java как тип «ArrayList» и в Python как тип «список».

Динамический массив может быть реализован с помощью структуры данных, состоящей из массива A элементов некоторой длины N вместе с числом n ≤ N , представляющим позиции в массиве, которые использовались до сих пор. С помощью этой структуры произвольный доступ к динамическому массиву может быть реализован путем доступа к одной и той же ячейке внутреннего массива A , а когда n < N, операция, которая увеличивает размер динамического массива, может быть реализована просто путем увеличения n . Однако, когда n = N , необходимо изменить размер A , и распространенная стратегия для этого — удвоить его размер, заменив A новым массивом длиной 2 n .

Эту структуру можно проанализировать с помощью потенциальной функции:

Φ = 2 п - N

Поскольку стратегия изменения размера всегда приводит к тому, что A будет заполнен как минимум наполовину, эта потенциальная функция всегда неотрицательна, как и хотелось.

Если операция увеличения размера не приводит к операции изменения размера, Φ увеличивается на 2, что является константой. Таким образом, постоянное фактическое время операции и постоянное увеличение потенциала в совокупности дают постоянное амортизированное время для операции этого типа.

Однако когда операция увеличения размера вызывает изменение размера, потенциальное значение Φ уменьшается до нуля после изменения размера. Выделение нового внутреннего массива A и копирование всех значений из старого внутреннего массива в новый занимает фактическое время O( n ), но (при соответствующем выборе константы пропорциональности C ) это полностью компенсируется уменьшением потенциальную функцию, оставляя постоянное общее амортизированное время для операции.

Остальные операции структуры данных (чтение и запись ячеек массива без изменения размера массива) не вызывают изменения потенциальной функции и имеют такое же постоянное амортизированное время, что и их фактическое время.

Следовательно, при таком выборе стратегии изменения размера и потенциальной функции потенциальный метод показывает, что все операции с динамическими массивами занимают постоянное амортизированное время. Объединив это с неравенством, связывающим амортизированное время и фактическое время для последовательностей операций, это показывает, что любая последовательность из n операций с динамическими массивами в худшем случае занимает O( n ) фактического времени, несмотря на то, что некоторые из отдельных операций сами по себе могут занимать линейный промежуток времени.

Когда динамический массив включает в себя операции, которые уменьшают, а также увеличивают его размер, потенциальную функцию необходимо изменить, чтобы она не стала отрицательной. Один из способов сделать это — заменить приведенную выше формулу для Φ ее абсолютным значением .

Мультипоп-стек

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

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

Pop( k ) требует времени O( k ), но мы хотим показать, что все операции занимают амортизированное время O(1).

Эту структуру можно проанализировать с помощью потенциальной функции:

Φ = количество элементов в стеке

Это число всегда неотрицательно, как и требуется.

Операция Push занимает постоянное время и увеличивает Φ на 1, поэтому ее амортизированное время является постоянным.

Операция Pop занимает время O( k ), но также уменьшает Φ на k , поэтому ее амортизированное время также является постоянным.

Это доказывает, что любая последовательность из m занимает O( m операций в худшем случае ) фактического времени.

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

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

• Инициализация: создайте счетчик со значением 0.
• Inc: добавьте 1 к счетчику.
• Чтение: вернуть текущее значение счетчика.

В этом примере мы не используем трансдихотомическую машинную модель , а вместо этого требуем одну единицу времени на битовую операцию в приращении. Мы хотим показать, что Inc занимает амортизированное время O(1).

Эту структуру можно проанализировать с помощью потенциальной функции:

Φ = количество битов, равное 1 = вес Хэмминга (счетчик)

Это число всегда неотрицательно и начинается с 0, как и требуется.

Операция Inc инвертирует младший бит . Затем, если младший бит был инвертирован с 1 на 0, то следующий бит также инвертируется. Это продолжается до тех пор, пока бит не изменится с 0 на 1, после чего переворот прекращается. Если счетчик первоначально заканчивается на k 1 битах, мы переворачиваем в общей сложности k +1 бит, беря фактическое время k +1 и уменьшая потенциал на k -1, так что амортизированное время равно 2. Следовательно, фактическое время для выполнения m Inc операций составляет O( m ).

Приложения

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