Изменения
→Оценка сложности
Сложность первой итерации алгоритма — <tex> O(E^2) </tex>.
|proof=
На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq V </tex>. Поиск каждого дополнительного пути требует <tex> O(E) </tex> времени, а их количество не больше <tex> V </tex>. Итоговая сложность первой итерации — <tex> O(VE) \leq O(E^2) </tex>, q.e.d.
}}
<tex> \langle A, \overline{A} \rangle </tex> — [[Разрез,_лемма_о_потоке_через_разрез|разрез]], значит:
<tex> |f'_1| = f'_1(A, \overline{A}) \leq c(A, \overline{A}) \leq E, f_1 = f_0 + f'_1 </tex>.
Пропускная способность каждого дополняющего пути не меньше <tex> 1 </tex>, а поиск каждого занимает <tex> O(E) </tex> времени. Значит, итоговое время работы — <tex> O(E^2) </tex>, q.e.d.
}}
Оценка сложности остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общая сложность алгоритма — <tex> O(E^2 \log U) </tex>, q.e.d.
}}
