272
правки
Изменения
→Оценка сложности
{{Утверждение
|statement=
|proof=
Докажем, что сложность время работы каждой итерации — <tex> O(E^2) </tex>.
{{Лемма
|statement=
|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>.
}}
{{Лемма
|statement=
[[Файл:Scaling.jpg|250px|thumb|right|Разрез <tex> \langle A, \overline{A} \rangle </tex>.]]
Докажем оценку для второго шага (для остальных доказательство аналогично).
}}
Оценка сложности времени работы остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общая сложность общее время работы алгоритма — <tex> O(E^2 \log U) </tex>.
}}
