272
правки
Изменения
→Оценка сложности
Количество итераций — <tex> O(\log U) </tex>. Докажем, что сложность каждой итерации — <tex> O(E^2) </tex>.
На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| </tex>. Поиск каждого дополнительного пути занимает <tex> O(E) </tex>, а их количество не больше <tex> V </tex>.Итоговая сложность первой итерации — <tex> O(VE) \leq O(E^2) </tex>.
}}
