Потенциальный метод

В теории вычислительной сложности потенциальный метод — это метод, используемый для анализа амортизированной временной и пространственной сложности структуры данных , меры ее производительности в последовательностях операций, которая сглаживает стоимость редких, но дорогих операций. ^{[1] [2]}

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

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

${\displaystyle T_{\mathrm {амортизированный} }(o)=T_{\mathrm {фактич.} }(o)+C\cdot (\Phi (S_{\mathrm {после} })-\Phi (S_{\mathrm {до} })),}$

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

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

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

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

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

Затем:

${\displaystyle T_{\mathrm {амортизировано} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {фактическое} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {фактическое} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}$

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

${\displaystyle T_{\mathrm {фактическое} }(O)=T_{\mathrm {амортизированное} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}$

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

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

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

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

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

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

Ф = 2n  −  N

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

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

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

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

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

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

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

• Инициализация — создание пустого стека.
• 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 переворачивает младший бит . Затем, если LSB был перевернут с 1 на 0, то следующий бит также переворачивается. Это продолжается до тех пор, пока, наконец, бит не будет перевернут с 0 на 1, после чего переворачивание прекращается. Если счетчик изначально заканчивается на k 1 бит, мы переворачиваем в общей сложности k +1 бит, беря фактическое время k +1 и уменьшая потенциал на k −1, так что амортизированное время равно 2. Следовательно, фактическое время для выполнения m операций Inc равно O( m ).

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