338
правок
Изменения
→Анализ
== Анализ ==
{{Теорема
|statement =
Время выполнения операции <tex>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>relabelToFront</tex> выполняет работу (без учета операций вызываемых в <tex>discharge</tex>), за <tex>O(V^{3})</tex>.
Оценим работу выполнения внутри операции <tex>discharge</tex>:
#Обновление указателя <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>.
}}
== Источники ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
