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

В информатике амортизированный анализ — это метод анализа сложности заданного алгоритма или того , сколько ресурсов, особенно времени или памяти, требуется для его выполнения . Мотивация амортизированного анализа заключается в том, что рассмотрение наихудшего времени выполнения может быть слишком пессимистичным. Вместо этого амортизированный анализ усредняет время выполнения операций в последовательности по этой последовательности. ^[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), скопировать старые элементы в новый массив, а затем добавить новый элемент. Следующие три операции вставки также заняли бы постоянное время, а затем последующее добавление потребовало бы еще одного медленного удвоения размера массива.

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

Очередь

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

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

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

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

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

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

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

Ссылки

^ ab Tarjan, Robert Endre (апрель 1985 г.). "Amortized Computational Complexity" (PDF) . SIAM Journal on Algebraic and Discrete Methods . 6 (2): 306–318. doi :10.1137/0606031. Архивировано (PDF) из оригинала 26 февраля 2015 г. . Получено 9 июня 2024 г. .
^ abc Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF) , заархивировано из оригинала (PDF) 20 октября 2013 г. , извлечено 3 мая 2011 г.
^ abcde Kozen, Dexter (весна 2011 г.). "CS 3110 Lecture 20: Amortized Analysis". Cornell University . Получено 14 марта 2015 г. .
^ Гроссман, Дэн. "CSE332: Data Abstractions" (PDF) . cs.washington.edu . Получено 14 марта 2015 г. .

Литература

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