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

В информатике или того , амортизированный анализ — это метод анализа данного алгоритма сложности сколько ресурсов, особенно времени или памяти, требуется для его выполнения . Мотивацией для амортизированного анализа является то, что оценка времени выполнения в худшем случае может оказаться слишком пессимистической. Вместо этого амортизированный анализ усредняет время выполнения операций в последовательности по этой последовательности. ^[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 + 1 в массив размера n , мы заметим, что операции отправки занимают постоянное время, за исключением последней, которая занимает $\Theta (n)$ время для выполнения операции удвоения размера. Поскольку всего было n + 1 операций, мы можем взять среднее значение и обнаружить, что для помещения элементов в динамический массив требуется: ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (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]