Изменения
→Оценка быстродействия
{{Теорема
|statement =
Время выполнения операции <tex>\mathtt{relabelToFront}</tex> для любой сети <tex>G = (V, E)</tex> составляет <tex>O(V^{3})</tex>.
|proof =
Пусть '''фаза''' {{---}} время между двумя последовательными операциями подъема. Так как всего, по [[Метод проталкивания предпотока#Лемма6|лемме (6)]], выполняется <tex>O(V^{2})</tex> подъемов, значит, в алгоритме всего <tex>O(V^{2})</tex> фаз.
Если операция <tex>discharge</tex> не выполняет подъем, то следующий ее вызов происходит дальше по списку <tex>L</tex> <tex>(</tex>длина <tex>L</tex> меньше <tex>|V|)</tex>. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более <tex>|V|</tex> вызовов <tex>discharge</tex>.
Таким образом, цикл '''while''' процедуры <tex>\mathtt{relabelToFront}</tex> выполняет работу (без учета операций вызываемых в <tex>discharge</tex>), за <tex>O(V^{3})</tex>.
Оценим работу выполнения внутри операции <tex>discharge</tex>:
#Из [[Метод проталкивания предпотока#Лемма8|леммы (8)]] следует, что количество насыщающих проталкиваний составляет <tex>O(VE)</tex>. Ненасыщающее проталкивание уменьшает избыток до <tex>0</tex>, после чего разгрузка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов <tex>discharge</tex>, то есть <tex>O(V^{3})</tex>.
Таким образом, время выполнения операции <tex>\mathtt{relabelToFront}</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>.
}}
