最大二分匹配算法的时间复杂度是多少?

问题描述 投票:0回答:1

[这是经典问题:-“有M个求职者,N个求职者。每个求职者都有他/她感兴趣的一部分工作。每个职位空缺只能接受一个求职者,并且可以指定一个求职者仅一份工作。找到分配给申请人的工作,以使尽可能多的申请人获得工作。“

我正在使用以下代码和算法来解决问题:https://www.geeksforgeeks.org/maximum-bipartite-matching/

此算法的时间复杂度是多少?

matching bipartite
1个回答
0
投票

根据this维基百科文章,Ford&Fulkerson的算法的运行时复杂度为O(|E|f),其中|E|是输入边集的基数。请注意,此运行时范围取决于最佳值,并且是伪多项式。

© www.soinside.com 2019 - 2024. All rights reserved.