338
правок
Изменения
м
→Оценка быстродействия
#Обновление указателя <tex>current[u]</tex> выполняется <tex>O(deg(u))</tex> в том случае, когда вершина <tex>u</tex> подвергается подъему. Значит, для всех вершин время составляет <tex>O(V deg(u))</tex>. Следовательно, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], время равно <tex>O(VE)</tex>.
#Пусть <tex>u</tex> {{---}} произвольная вершина сети. Она может быть поднята не более <tex>O(V)</tex> раз, время каждого подъема <tex>O(deg(u))</tex>. Значит, время всех подъемов ограничивается <tex>O(VE)</tex>.
#Из [[Метод проталкивания предпотока#Лемма8|леммы (8)]] следует, что количество насыщающих проталкиваний составляет <tex>O(VE)</tex>. Ненасыщающее проталкивание уменьшает избыток до <tex>0</tex>, после чего разрядка разгрузка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов <tex>discharge</tex>, то есть <tex>O(V^{3})</tex>.
Таким образом, время выполнения операции <tex>relabelToFront</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>.
