Амортизированный анализ

В информатике или того , амортизированный анализ — это метод анализа данного алгоритма сложности сколько ресурсов, особенно времени или памяти, требуется для его выполнения . Мотивацией для амортизированного анализа является то, что оценка времени выполнения в худшем случае может оказаться слишком пессимистической. Вместо этого амортизированный анализ усредняет время выполнения операций в последовательности по этой последовательности. ^{[ 1 ]}^: 306 В заключение: «Амортизированный анализ — полезный инструмент, дополняющий другие методы, такие как анализ наихудшего и среднего случая ». ^{[ 2 ]}^: 14

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

История

Амортизированный анализ первоначально возник на основе метода, называемого агрегатным анализом, который сейчас отнесен к амортизированному анализу. Этот метод был впервые официально представлен Робертом Тарджаном в его статье 1985 года «Амортизированная вычислительная сложность» . ^{[ 1 ]} который рассматривал необходимость в более полезной форме анализа, чем используемые обычные вероятностные методы. Первоначально амортизация использовалась для очень специфических типов алгоритмов, особенно для тех, которые связаны с двоичными деревьями и объединения операциями . Однако сейчас он распространен повсеместно и используется и при анализе многих других алгоритмов. ^{[ 2 ]}

Метод

Амортизированный анализ требует знания того, какие серии операций возможны. Чаще всего это происходит со структурами данных , состояние которых сохраняется между операциями. Основная идея состоит в том, что операция в худшем случае может изменить состояние таким образом, что худший случай не сможет повториться в течение длительного времени, таким образом «амортизируя» его стоимость.

Обычно существует три метода проведения амортизированного анализа: агрегированный метод, метод бухгалтерского учета и потенциальный метод . Все это дает правильные ответы; выбор того, что использовать, зависит от того, что наиболее удобно для конкретной ситуации. ^{[ 3 ]}

Совокупный анализ определяет верхнюю границу T ( n ) общей стоимости последовательности из n операций, затем вычисляет амортизированную стоимость как T ( n ) / n . ^{[ 3 ]}
Метод бухгалтерского учета представляет собой форму совокупного анализа, при которой каждой операции присваивается амортизированная стоимость , которая может отличаться от ее фактической стоимости. Ранние операции имеют амортизированную стоимость выше их фактической стоимости, что накапливает сэкономленный «кредит», который оплачивает более поздние операции, имеющие амортизированную стоимость ниже их фактической стоимости. Поскольку кредит начинается с нуля, фактическая стоимость последовательности операций равна амортизированной стоимости за вычетом накопленного кредита. Поскольку кредит должен быть неотрицательным, амортизированная стоимость является верхней границей фактической стоимости. Обычно многие краткосрочные операции накапливают такой кредит небольшими порциями, в то время как редкие долгосрочные операции резко уменьшают его. ^{[ 3 ]}
Потенциальный метод — это форма метода бухгалтерского учета, при которой сэкономленный кредит рассчитывается как функция («потенциал») состояния структуры данных. Амортизированная стоимость представляет собой непосредственную стоимость плюс изменение потенциала. ^{[ 3 ]}

Примеры

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

Амортизированный анализ операции push для динамического массива

Рассмотрим динамический массив , размер которого увеличивается по мере добавления к нему новых элементов, например ArrayList на Яве или std::vector в С++. Если бы мы начали с динамического массива размером 4, мы могли бы поместить в него 4 элемента, и каждая операция заняла бы постоянное время . Однако добавление пятого элемента в этот массив займет больше времени, поскольку массиву придется создать новый массив вдвое большего текущего размера (8), скопировать старые элементы в новый массив, а затем добавить новый элемент. Следующие три операции push также займут постоянное время, а затем последующее добавление потребует еще одного медленного удвоения размера массива.

В общем случае для произвольного числа $n$ перемещений в массив любого начального размера, время шагов, удваивающих массив, складывается в прогрессию геометрическую $O(n)$ , в то время как постоянное время для каждого оставшегося нажатия также добавляется к $O(n)$ . Следовательно, среднее время на операцию нажатия равно $O(n)/n=O(1)$ . Эти рассуждения можно формализовать и обобщить на более сложные структуры данных с помощью амортизированного анализа. ^{[ 3 ]}

Очередь

Показана реализация Queue на Python3 , структуры данных FIFO :

class Queue:
  # Initialize the queue with two empty lists
  def __init__(self):
    self.input = [] # Stores elements that are enqueued
    self.output = [] # Stores elements that are dequeued

  def enqueue(self, element):
    self.input.append(element) # Append the element to the input list

  def dequeue(self):
    if not self.output: # If the output list is empty
      # Transfer all elements from the input list to the output list, reversing the order
      while self.input: # While the input list is not empty
        self.output.append(self.input.pop()) # Pop the last element from the input list and append it to the output list
    
    return self.output.pop() # Pop and return the last element from the output list

Операция постановки в очередь просто помещает элемент во входной массив; эта операция не зависит от длины входных или выходных данных и поэтому выполняется за постоянное время.

Однако операция удаления из очереди более сложна. Если выходной массив уже содержит некоторые элементы, удаление из очереди выполняется за постоянное время; в противном случае удаление из очереди занимает ⁠ $O(n)$ ⁠ время добавить все элементы в выходной массив из входного массива, где n — текущая длина входного массива. После копирования n элементов из входных данных мы можем выполнить n операций удаления из очереди, каждая из которых занимает постоянное время, прежде чем выходной массив снова станет пустым. Таким образом, мы можем выполнить последовательность из n операций удаления из очереди всего за ⁠ $O(n)$ ⁠ время, что означает, что амортизированное время каждой операции удаления из очереди составляет ⁠ $O(1)$ ⁠ . ^{[ 4 ]}

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

Общее использование

В обычном использовании «амортизированный алгоритм» — это алгоритм, который, как показал амортизированный анализ, работает хорошо.
Онлайн-алгоритмы обычно используют амортизированный анализ.

Ссылки

^ Перейти обратно: ^а ^б Тарьян, Роберт Эндре (апрель 1985 г.). «Амортизированная сложность вычислений» (PDF) . SIAM Journal по алгебраическим и дискретным методам . 6 (2): 306–318. дои : 10.1137/0606031 . Архивировано (PDF) из оригинала 26 февраля 2015 года . Проверено 9 июня 2024 г.
^ Перейти обратно: ^а ^б ^с Ребекка Фибринк (2007), Объяснение амортизированного анализа (PDF) , заархивировано из оригинала (PDF) 20 октября 2013 г. , получено 3 мая 2011 г.
^ Перейти обратно: ^а ^б ^с ^д ^и Козен, Декстер (весна 2011 г.). «CS 3110 Лекция 20: Амортизированный анализ» . Корнеллский университет . Проверено 14 марта 2015 г.
^ Гроссман, Дэн. «CSE332: Абстракции данных» (PDF) . cs.washington.edu . Проверено 14 марта 2015 г.

Литература

«Лекция 7: Амортизированный анализ» (PDF) . Университет Карнеги-Меллон . Проверено 14 марта 2015 г.
Аллан Бородин и Ран Эль-Янив (1998). Онлайн-вычисления и конкурентный анализ . стр. 20, 141.

[tarjan-1] Перейти обратно: ^а ^б Тарьян, Роберт Эндре (апрель 1985 г.). «Амортизированная сложность вычислений» (PDF) . SIAM Journal по алгебраическим и дискретным методам . 6 (2): 306–318. дои : 10.1137/0606031 . Архивировано (PDF) из оригинала 26 февраля 2015 года . Проверено 9 июня 2024 г.

[fiebrink-2] Перейти обратно: ^а ^б ^с Ребекка Фибринк (2007), Объяснение амортизированного анализа (PDF) , заархивировано из оригинала (PDF) 20 октября 2013 г. , получено 3 мая 2011 г.

[Lecture_20-3] Перейти обратно: ^а ^б ^с ^д ^и Козен, Декстер (весна 2011 г.). «CS 3110 Лекция 20: Амортизированный анализ» . Корнеллский университет . Проверено 14 марта 2015 г.

[Grossman-4] Гроссман, Дэн. «CSE332: Абстракции данных» (PDF) . cs.washington.edu . Проверено 14 марта 2015 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]