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

В информатике , амортизируется анализ представляет собой метод анализа заданного алгоритма сложности , или сколько ресурса, особенно времени или памяти, требуется для выполнения . Мотивация для амортизированного анализа заключается в том, что рассмотрение наихудшего времени выполнения каждой операции , а не алгоритма , может быть слишком пессимистичным. ^[1]

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

История [ править ]

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

Метод [ править ]

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

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

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

Примеры [ править ]

Динамический массив [ править ]

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

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

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

Очередь [ править ]

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

class  Queue  def  initialize  @input  =  []  @output  =  []  end def  enqueue ( элемент )  @input  <<  конец элемента  def  dequeue,  если  @output . пустой?  а  @input . любой?  @output  <<  @input . поп-  энд-  энд @ выход . поп-  энд- энд

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

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

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

Обычное использование [ править ]

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

Ссылки [ править ]

• Аллан Бородин и Ран Эль-Янив (1998). Онлайн-вычисления и конкурентный анализ . Издательство Кембриджского университета. С. 20, 141.