Изменения

Поиск максимального паросочетания или минимального контролирующего множества в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика работы алгоритма — <tex> O(n^4) </tex>.

Предложенный метод корректен, но не является оптимальным по времени работы, оно может быть улучшено до <tex> O(n^3) </tex>.