Возможный метод - Potential method

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

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

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

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

{displaystyle T_ {mathrm {amortized}} (o) = T_ {mathrm {actual}} (o) + Ccdot (Phi (S_ {mathrm {after}}) - Phi (S_ {mathrm {before}})),}

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

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

Соотношение амортизированного и фактического времени

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

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

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

Потом:

{displaystyle T_ {mathrm {amortized}} (O) = sum _ {i = 1} ^ {n} left (T_ {mathrm {actual}} (o_ {i}) + Ccdot (Phi (S_ {i}) - Phi (S_ {i-1})) ight) = T_ {mathrm {actual}} (O) + Ccdot (Phi (S_ {n}) - Phi (S_ {0})),}

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

{displaystyle T_ {mathrm {actual}} (O) = T_ {mathrm {amortized}} (O) -Ccdot (Phi (S_ {n}) - Phi (S_ {0})).}

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

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

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

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

Примеры

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

А динамический массив это структура данных для поддержки массив предметов, позволяя как произвольный доступ на позиции в массиве и возможность увеличения размера массива на единицу. Он доступен в Ява как тип "ArrayList" и в Python как тип «список».

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

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

Φ = 2п − N

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Φ = число битов, равное 1 = Hammingweight (счетчик)

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

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

Приложения

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

использованная литература

^ ^а ^б ^c Гудрич, Майкл Т.; Тамассия, Роберто (2002), «1.5.1 Методы амортизации», Разработка алгоритмов: основы, анализ и примеры в Интернете, Wiley, стр. 36–38..
^ ^а ^б ^c ^d ^е Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «17.3 Потенциальный метод». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 412–416. ISBN 0-262-03293-7.
^ Гудрич и Тамассия, 1.5.2 Анализ реализации расширяемого массива, стр. 139–141; Кормен и др., 17.4 Динамические таблицы, стр. 416–424.
^ Кормен и др., Глава 20, «Кучи Фибоначчи», стр. 476–497.
^ Гудрич и Тамассия, Раздел 3.4, «Раскидистые деревья», стр. 185–194.

[gt-ad-1] а ^б ^c Гудрич, Майкл Т.; Тамассия, Роберто (2002), «1.5.1 Методы амортизации», Разработка алгоритмов: основы, анализ и примеры в Интернете, Wiley, стр. 36–38..

[clrs-2] а ^б ^c ^d ^е Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «17.3 Потенциальный метод». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 412–416. ISBN 0-262-03293-7.

[3] Гудрич и Тамассия, 1.5.2 Анализ реализации расширяемого массива, стр. 139–141; Кормен и др., 17.4 Динамические таблицы, стр. 416–424.

[4] Кормен и др., Глава 20, «Кучи Фибоначчи», стр. 476–497.

[5] Гудрич и Тамассия, Раздел 3.4, «Раскидистые деревья», стр. 185–194.

[1]

[2]

[3]

[4]

[5]