Что такое амортизированный анализ? И как это может помочь мне достичь наихудших гарантий производительности в моих программах?
Я читал, что следующие методы могут помочь программисту достичь гарантий производительности в худшем случае (то есть, по моим собственным словам: гарантировать, что время выполнения программы не превысит время выполнения в худшем случае):
- Рандомизированные алгоритмы (например, алгоритм быстрой сортировки является квадратичным в наихудшем случае, но случайное упорядочение входных данных дает вероятностную гарантию того, что время его работы является линейным)
- Последовательности операций (наш анализ должен учитывать как данные, так и последовательность операций, выполняемых клиентом)
- Амортизированный анализ (еще один способ предоставления гарантии производительности - амортизация стоимости путем отслеживания общей стоимости всех операций, деленной на количество операций. В этом параметре мы можем разрешить некоторые дорогостоящие операции, сохраняя при этом среднюю стоимость операций на низком уровне. Другими словами, мы распределяем стоимость нескольких дорогостоящих операций, назначая часть их каждой из большого количества недорогих операций).
Автор упомянул использование структуры данных массива изменения размеров для стека в качестве одного из примеров того, как выполнить амортизированный анализ, но я до сих пор не понимаю, что такое амортизированный анализ и как его можно реально реализовать (структура данных? Алгоритм?) Для достижения худшего гарантия исполнения