Какова временная сложность алгоритма согласования максимального двудольного ie

Question

Вот классическая проблема: - «Есть M соискателей и N вакансий. У каждого соискателя есть подмножество вакансий, которые его / ее интересуют. Каждое вакансия может принять только одного соискателя, и соискатель может быть назначен». только для одной работы. Найдите распределение заданий для кандидатов таким образом, чтобы как можно больше вакансий получили работу. "

Я использую следующий код и алгоритм для решения проблемы: https://www.geeksforgeeks.org/maximum-bipartite-matching/

Какова будет временная сложность этого алгоритма?

Answer 1

Согласно этой статье в Википедии, алгоритм Ford & Fulkerson имеет сложность времени выполнения O(|E|f), где |E| - количество элементов набора входов. Обратите внимание, что эта граница времени выполнения зависит от оптимального значения и является псевдополиномиальной.