272
правки
Изменения
→Оценка времени работы
Время работы алгоритма {{---}} <tex> O(E^2 \log U) </tex>.
|proof=
Пусть <tex> S = \{2^{\lfloor \log_2 U \rfloor}, \ldots, 2^k, \ldots, 2, 1, 0\} </tex> {{---}} множество уровнеймасштабов. Тогда <tex> |S| </tex> {{---}} количество итераций алгоритма.
{{Лемма
2
|statement=
Количество увеличивающих дополняющих путей на с масштабом <tex> 2^k </tex>-ом уровне не превосходит <tex> 2E </tex>.
|proof=
Каждый увеличивающий дополняющий путь на <tex> k </tex>-ом уровне имеет пропускную способность не меньше <tex> 2^k </tex>.На предыдущей итерации дополняющий поток ограничен значением <tex> 2^{k + 1} E </tex> по предыдущей лемме. Следовательно, количество дополняющих путей не превосходит <tex> 2E </tex>.
}}
Общее количество увеличивающих путей не превышает <tex> O(E \log U) </tex>.
|proof=
Следует из предыдущей леммы и факта, что количество уровней итераций {{---}} <tex> O(\log U) </tex>.
}}
