Изменения

Докажем, что амортизированное время работы операции <tex>decreaseKey</tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.

Пусть мы вызвали процедуру каскадного вырезания <tex> k </tex> раз. Тогда вершин с пометкой Так как реальное время работы операции <tex> x.mark = true cascadingCut </tex> стало на без учета рекурсии составляет <tex> k O(1) </tex> меньше, а в корневом списке прибавилось то реальное время работы операции <tex> k decreaseKey </tex> новых вершин. Итого, время работы будет: <tex> O(k) + \Phi_i {{-- \Phi_{i - 1} = O(k) + (k - 2k + O(1)) </tex>. Следовательно, амортизированная стоимость не превышает } <tex> O(1k) </tex>, поскольку мы можем соответствующим образом масштабировать единицы потенциала.

На языке метода предоплаты: пусть у каждого узла Рассмотрим, как изменится потенциал в списке корней лежит монета, а у каждой помеченной вершины результате выполнения данной операции. Пусть <tex> H </tex> {{---}} 2 монетыфибоначчиева куча до вызова <tex> decreaseKey </tex>. Покажем, что взяв 4 монеты за операцию Тогда после <tex> k </tex> рекурсивных вызовов операции <tex> decreaseKey cascadingCut </tex>, мы сможем оплатить эту операциювершин с пометкой <tex> x. Одну монету потратим mark = true </tex> стало как минимум на перенос в корневой список и релаксацию минимума<tex> k - 2 </tex> меньше, потому что каждый вызов каскадного вырезания, за исключением последнего, еще 1 {{---}} уменьшает количество помеченных вершин на тоодну, чтобы положить монету у новой вершины и в результате последнего вызова одну вершину мы можем пометить. В корневом списке, которую мы потратим на следующую операцию прибавилось <tex>extractMink </tex>. У нас осталось 2 монеты. Далее производим каскадное вырезание: в случае, когда новых деревьев (<tex> x.p.mark = false k - 1 </tex>, кладем 2 монеты к этой вершине, дерево за счет каскадного вырезания и устанавливаем соответствующую пометку. Инвариант сохраняетсяеще одно из-за самого первого вызова операции <tex> cut </tex>).

ИначеВ итоге, добавляем к помеченной вершине родителя еще изменение потенциала составляет: <tex> \Phi_i - \Phi_{i - 1} = ((t[H] + k) + 2 монеты(m[H] + k - 2)) - (t[H] + 2m[H]) = 4 - k </tex>. В итогеСледовательно, в родительском узле становится амортизированная стоимость не превышает <tex> O(k) + 4 монеты, и - k </tex>. Но поскольку мы можем рекурсивно продолжить данный процесс. Оценка доказанасоответствующим образом масштабировать единицы потенциала, то амортизированная стоимость операции <tex> decreaseKey </tex> равна <tex> O(1) </tex>.