403
правки
Изменения
→Оценка быстродействия
Зная верхнюю границу величины <tex> \Phi </tex>, ее значение после выполнения алгоритма и то, что при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается минимум на единицу, то можно сделать вывод, что количество ненасыщающих проталкиваний не больше чем <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
}}
{{Теорема
|statement =
Пусть <tex> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> pushRelabelMaxFlow </tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>
|proof =
Из [[#Лемма6|леммы (6)]], [[#Лемма8|леммы (8)]] и [[#Лемма9|леммы (9)]] следует, что число операций подъема и проталкиваний не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 + 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert + 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) = O(V^2E) </tex>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
}}
