Амортизированный анализ
В компьютерных науках амортизированный анализ — это метод анализа сложности данного алгоритма или того, сколько ресурсов, особенно времени или памяти, требуется для выполнения . Мотивация амортизированного анализа заключается в том, что рассмотрение времени выполнения в наихудшем случае может быть слишком пессимистичным. Вместо этого амортизированный анализ усредняет время выполнения операций в последовательности по этой последовательности. [1] : 306 В заключение: «Амортизированный анализ является полезным инструментом, который дополняет другие методы, такие как анализ наихудшего и среднего случая ». [2] : 14
Для данной операции алгоритма определенные ситуации (например, входные параметризации или содержимое структуры данных) могут потребовать значительных затрат ресурсов, тогда как другие ситуации могут быть не такими затратными. Амортизированный анализ рассматривает как дорогостоящие, так и менее затратные операции вместе по всей последовательности операций. Это может включать учет различных типов ввода, длины ввода и других факторов, влияющих на его производительность. [2]
Первоначально амортизированный анализ возник из метода, называемого совокупным анализом, который теперь включен в амортизированный анализ. Этот метод был впервые официально представлен Робертом Тарьяном в его статье 1985 года « Амортизированная вычислительная сложность » [1] , в которой рассматривалась потребность в более полезной форме анализа, чем обычные используемые вероятностные методы. Амортизация изначально использовалась для очень специфических типов алгоритмов, особенно для тех, которые включают бинарные деревья и операции объединения . Однако теперь он используется повсеместно и также используется при анализе многих других алгоритмов. [2]
Амортизационный анализ требует знания того, какие серии операций возможны. Чаще всего это происходит со структурами данных , состояние которых сохраняется между операциями. Основная идея состоит в том, что операция в наихудшем случае может изменить состояние таким образом, что наихудший случай не может повториться в течение длительного времени, тем самым «амортизируя» свою стоимость.
Обычно существует три метода проведения амортизированного анализа: совокупный метод, учетный метод и потенциальный метод . Все они дают правильные ответы; выбор того, что использовать, зависит от того, что наиболее удобно для конкретной ситуации. [3]
Рассмотрим динамический массив , размер которого увеличивается по мере добавления к нему новых элементов, например, ArrayListв Java или std::vectorC++. Если бы мы начали с динамического массива размером 4, мы могли бы поместить в него 4 элемента, и каждая операция заняла бы постоянное время . Тем не менее, добавление пятого элемента в этот массив заняло бы больше времени, так как массив должен был бы создать новый массив в два раза больше текущего размера (8), скопировать старые элементы в новый массив, а затем добавить новый элемент. Следующие три операции push также будут занимать постоянное время, а затем последующее добавление потребует еще одного медленного удвоения размера массива.
