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

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

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

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

История

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

Метод

Основные статьи: Метод учета (информатика) и метод потенциала.

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

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

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

Примеры

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

Амортизированный анализ операции 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)$, постоянное время.

Хвост

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

class   Queue  :    # Инициализируем очередь двумя пустыми списками    def   __init__  (  self  ):      self  .  input   =   []   # Сохраняет элементы, поставленные в очередь      self  .  output   =   []   # Сохраняет элементы, исключенные из очереди,    def   enqueue  (  self  ,   element  ):      self  .  вход  .  append  (  element  )   # Добавляем элемент в список ввода    def   dequeue  (  self  ):      if   not   self  .  output  :   # Если выходной список пуст        # Перенесите все элементы из входного списка в выходной список, меняя порядок на обратный,        пока   self  .  input  :   # Пока список ввода не пуст,          self  .  выход  .  append  (  self.input.pop  #  Извлекаем последний элемент из входного списка и добавляем его в  )  (  ))   выходной список          return   self  .  выход  .  pop  ()   # Извлекаем и возвращаем последний элемент из выходного списка 

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

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

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

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

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

Литература

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