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