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

Метод анализа алгоритмов в информатике

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

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

История

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

Метод

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

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

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

Примеры

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

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

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

В общем, если мы рассмотрим произвольное количество отправок n + 1 в массив размера n , мы заметим, что операции отправки занимают постоянное время, за исключением последней, которая требует времени для выполнения операции удвоения размера. Поскольку всего было n + 1 операций, мы можем взять среднее значение и обнаружить, что помещение элементов в динамический массив занимает: , постоянное время. ^[3] ${\displaystyle \Theta (n)}$ ${\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$

Очередь

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

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

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

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

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

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

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

Рекомендации

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

Литература

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