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>.
}}
