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

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

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

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

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

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

Однако операция удаления из очереди более сложна. Если в выходном массиве уже есть какие-то элементы, то удаление из очереди выполняется за постоянное время; в противном случае удаление из очереди требует времени для добавления всех элементов в выходной массив из входного массива, где n - текущая длина входного массива. После копирования n элементов из ввода мы можем выполнить n операций удаления из очереди, каждая из которых занимает постоянное время, прежде чем выходной массив снова станет пустым. Таким образом, мы можем выполнить последовательность из n операций удаления из очереди только за время, что означает, что амортизированное время каждой операции удаления из очереди равно . [5]

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

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

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

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

  • Аллан Бородин и Ран Эль-Янив (1998). Онлайн-вычисления и конкурентный анализ . Издательство Кембриджского университета. С. 20, 141.
  1. ^ «Лекция 7: Амортизированный анализ» (PDF) . Университет Карнеги-Меллона . Проверено 14 марта 2015 года .
  2. ^ a b Ребекка Фибринк (2007), Объяснение амортизированного анализа (PDF) , заархивировано из оригинала (PDF) 20 октября 2013 г. , извлечено 3 мая 2011 г.
  3. ^ Тарджан, Роберт Эндре (апрель 1985). «Амортизированная вычислительная сложность» (PDF) . Журнал SIAM по алгебраическим и дискретным методам . 6 (2): 306–318. DOI : 10.1137 / 0606031 .
  4. ^ a b c d e Козен, Декстер (весна 2011 г.). «CS 3110 Лекция 20: Амортизированный анализ» . Корнельский университет . Проверено 14 марта 2015 года .
  5. ^ Гроссман, Дэн. «CSE332: абстракции данных» (PDF) . cs.washington.edu . Проверено 14 марта 2015 года .