Почему мы проводим амортизированный анализ для кучи Фибоначчи?
В Фибоначчи кучи для всех операций анализа амортизируются по своей природе. Почему у нас не может быть нормального анализа, как в случае биномиальной кучи.
1 ответ
В биномиальной куче каждая операция гарантированно выполняется с определенной наихудшей производительностью. Вставка никогда не займет больше времени O(log n), слияние никогда не займет больше времени O(log n + log m) и т. Д. Поэтому, когда анализируется эффективность биномиальной кучи, обычно используют более традиционный алгоритмический анализ.
Тем не менее, есть несколько свойств биномиальных куч, которые проявляются только при выполнении амортизированного анализа. Например, какова стоимость выполнения n последовательных вставок в биномиальную кучу, при условии, что куча изначально пуста? Вы можете показать, что в этом случае амортизированная стоимость вставки равна O(1), а это означает, что общая стоимость выполнения n вставок равна O(n). В этом смысле использование амортизированного анализа поверх традиционного анализа позволяет получить более глубокое представление о структуре данных, чем могло бы первоначально возникнуть из более консервативного анализа наихудшего случая.
В некотором смысле кучи Фибоначчи лучше всего анализировать в амортизированном смысле, потому что, хотя наихудшие границы для многих операций на самом деле не так уж велики (например, клавиша "Удалить" или "Уменьшение" может занять время Θ(n) в худшем случае) в любой серии операций куча Фибоначчи имеет превосходную амортизированную производительность. Даже если отдельное удаление-минут может занять Θ(n) времени, для серии m delete-min никогда не может потребоваться больше чем Θ(m log n) времени.
В другом смысле, однако, кучи Фибоначчи были специально разработаны, чтобы быть эффективными в амортизированном смысле, а не в худшем случае. Первоначально они были изобретены для ускорения алгоритмов Дейкстры и Прима, где все, что имело значение, это общая стоимость выполнения m ключей уменьшения и n удалений в куче n-узлов, и, поскольку это было целью проектирования, дизайнеры не пытались сделать кучи Фибоначчи эффективными в худшем случае.