При назначении амортизируемых затрат операциям со структурой данных необходимо обеспечить, чтобы для любой последовательности выполняемых операций сумма амортизируемых затрат всегда была не меньше суммы фактических затрат на эти операции.
Итак, давайте возьмем Вариант 1, который присваивает амортизированную стоимость O(1) вставкам и амортизированную стоимость O(log n) удалениям. Мы должны задать следующий вопрос: верно ли, что для любой последовательности операций над пустой двоичной кучей реальная стоимость этих операций ограничена сверху амортизированной стоимостью этих операций? И в этом случае ответ - нет. Представьте, что вы делаете последовательность из n вставок в кучу. Фактическая стоимость выполнения этих операций может быть Θ(n log n), если каждый элемент должен подниматься до вершины кучи. Однако амортизированная стоимость этих операций при такой схеме учета будет равна O(n), поскольку мы выполнили n операций и сделали вид, что каждая из них стоит O(1) времени. Следовательно, эта схема амортизированного учета не работает, так как позволяет недооценивать работу, которую мы делаем.
С другой стороны, давайте посмотрим на вариант 2, где мы назначаем O(log n) в качестве амортизированной стоимости вставки и O(1) в качестве амортизированной стоимости удаления. Теперь можем ли мы найти последовательность из n операций, где реальная стоимость этих операций превышает амортизированную стоимость? В этом случае ответ - нет. Вот один из способов увидеть это. Мы установили амортизированную стоимость вставки равной O(log n), что соответствует ее реальной стоимости, поэтому единственный способ, которым мы могли бы в конечном итоге занизить общую сумму, — это наша амортизированная стоимость удаления (O(1)). ), что ниже реальной стоимости удаления. Впрочем, здесь это не проблема. Чтобы мы могли выполнить операцию удаления, мы должны предварительно вставить удаляемый элемент. Совокупная реальная стоимость вставки и удаления равна O(log n) + O(log n) = O(log n), а совокупная амортизированная стоимость вставки и удаления равна O(log n) + O(1). ) = O (log n). Так что в этом смысле представление о том, что удаление происходит быстрее, не меняет наших общих затрат.
Хороший интуитивный способ понять, почему второй подход работает, а первый нет, — это подумать о том, что такое амортизированный анализ. Интуиция, стоящая за амортизацией, заключается в том, чтобы взимать немного больше за более ранние операции, чтобы будущие операции занимали меньше времени. В случае второй схемы учета именно это мы и делаем: мы смещаем стоимость удаления элемента из двоичной кучи обратно на стоимость вставки этого элемента в куче в первую очередь. Таким образом, поскольку мы только перемещаем работу назад, сумма амортизированных затрат не может быть ниже суммы реальных затрат. С другой стороны, в первом случае мы сдвигаем работу вперед во времени, заставляя удаления оплачивать вставки. Но это проблема, потому что, если мы сделаем кучу вставок, а затем никогда не сделаем соответствующих удалений, мы переложим работу на несуществующие операции.
person
templatetypedef
schedule
07.12.2020
