В теории сложности вычислений , то потенциальный метод представляет собой метод , используемый для анализа амортизированного времени и пространства сложности в виде структуры данных , измерение его производительности по сравнению с последовательностями операций, сглаживает стоимость нечастых , но дорогостоящие операции. [1] [2]
Определение амортизированного времени
В потенциальном методе выбирается функция Φ, которая отображает состояния структуры данных в неотрицательные числа. Если S - это состояние структуры данных, Φ ( S ) представляет работу, которая была учтена («оплачена») в амортизированном анализе, но еще не выполнена. Таким образом, Φ ( S ) можно рассматривать как вычисление количества потенциальной энергии, запасенной в этом состоянии. [1] [2] Потенциальное значение до операции инициализации структуры данных определяется равным нулю. В качестве альтернативы, Φ ( S ) можно представить как степень беспорядка в состоянии S или его расстояние от идеального состояния.
Пусть o будет любой отдельной операцией в последовательности операций над некоторой структурой данных, где S перед обозначением состояния структуры данных перед операцией o и S после обозначения ее состояния после завершения операции o . После выбора Φ амортизированное время операции o определяется как
где C - неотрицательная константа пропорциональности (в единицах времени), которая должна оставаться неизменной на протяжении всего анализа. То есть амортизированное время определяется как фактическое время, затраченное на операцию, плюс C, умноженное на разность потенциалов, вызванную операцией. [1] [2]
При изучении асимптотической вычислительной сложности с использованием большой нотации O постоянные множители не имеют значения, поэтому константа C обычно опускается.
Соотношение амортизированного и фактического времени
Несмотря на его искусственный вид, общее амортизированное время последовательности операций обеспечивает допустимую верхнюю границу фактического времени для той же последовательности операций.
Для любой последовательности операций , определять:
- Общее амортизированное время:
- Общее фактическое время:
Потом:
где последовательность значений потенциальной функции образует телескопический ряд, в котором все члены, кроме начального и конечного значений потенциальной функции, сокращаются попарно. Переставляя это, получаем:
С а также , , поэтому амортизированное время можно использовать для обеспечения точной верхней границы фактического времени последовательности операций, даже если амортизированное время для отдельной операции может значительно отличаться от фактического времени.
Амортизированный анализ исходных данных наихудшего случая
Как правило, амортизированный анализ используется в сочетании с предположением о наихудшем случае относительно входной последовательности. При этом предположении, если 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 . [3]
Эта структура может быть проанализирована с помощью потенциальной функции:
- Φ = 2 п - N
Поскольку стратегия изменения размера всегда приводит к тому, что A заполняется хотя бы наполовину, эта потенциальная функция всегда неотрицательна, как и требуется.
Когда операция увеличения размера не приводит к операции изменения размера, Φ увеличивается на 2, постоянное значение. Следовательно, постоянное фактическое время операции и постоянное увеличение потенциала в совокупности дают постоянное амортизированное время для операции этого типа.
Однако, когда операция увеличения размера вызывает изменение размера, потенциальное значение n уменьшается до нуля после изменения размера. Выделение нового внутреннего массива 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 переворачивает младший бит . Затем, если младший бит был перевернут с 1 на 0, то следующий бит также перевернется. Это продолжается до тех пор, пока, наконец, бит не изменится с 0 на 1, после чего переключение прекратится. Если счетчик изначально заканчивается на k 1 бит, мы переворачиваем всего k +1 бит, принимая фактическое время k +1 и уменьшая потенциал на k -1, так что амортизированное время равно 2. Следовательно, фактическое время выполнения m Inc операций составляет O ( m ).
Приложения
Метод потенциальных функций обычно используется для анализа кучи Фибоначчи , формы очереди с приоритетами, в которой удаление элемента занимает логарифмическое амортизированное время, а все другие операции занимают постоянное амортизированное время. [4] Его также можно использовать для анализа расширяемых деревьев , самонастраивающейся формы двоичного дерева поиска с логарифмической амортизацией времени на операцию. [5]
Рекомендации
- ^ a b c Гудрич, Майкл Т .; Тамассия, Роберто (2002), «1.5.1 Методы амортизации», Разработка алгоритмов: основы, анализ и примеры в Интернете , Wiley, стр. 36–38..
- ^ а б в г д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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.