为什么以下最大二部匹配实现O（m * n^2）的时间复杂度？

这个库有许多算法的实现，其中一个是最大的二分匹配。为什么以下最大二部匹配实现O（m * n^2）的时间复杂度？

这里是链接到源代码：http://shygypsy.com/tools/bpm.cpp

我会在这里将它包括在内（不评论）

#include <string.h> 

#define M 128 
#define N 128 

bool graph[M][N]; 
bool seen[N]; 
int matchL[M], matchR[N]; 
int n, m; 

bool bpm(int u) 
{ 
    for(int v = 0; v < n; v++) 
    if(graph[u][v]) 
    { 
    if(seen[v]) continue; 
    seen[v] = true; 

    if(matchR[v] < 0 || bpm(matchR[v])) 
    { 
     matchL[u] = v; 
     matchR[v] = u; 
     return true; 
    } 
} 
return false; 
} 

int main() 
{ 
    memset(matchL, -1, sizeof(matchL)); 
    memset(matchR, -1, sizeof(matchR)); 
    int cnt = 0; 
    for(int i = 0; i < m; i++) 
    { 
     memset(seen, 0, sizeof(seen)); 
     if(bpm(i)) cnt++; 
    } 
    return 0; 
}

我们有一个用于运行m次循环。数字m指的是工人的数量。然后我们输入bpm函数，它有另一个for循环。此循环运行n次，其中n是任务的数量。

直到现在我们有m*n时间复杂度。

但是在第三个if语句中有一个bpm的递归函数调用。此功能的目标是运行dfs以查找增强路径。

我知道dfs的时间复杂度为O(n+m)。所以我会假设函数bpm拥有的O(n+m)

复杂性。因此总的时间复杂度将是O(m*(n+m))

但是笔者认为这是O(m*n^2)。有人能解释我为什么会这样吗？先谢谢你！

来源

2013-03-10 ksm001

我会注意到'O（m *（n + m））== O（n * m^2）'，所以有没有你和作者有交换符号的机会吗？ – Simon 2013-03-10 19:36:49

如果我理解正确，m是工人的数量，n是任务的数量，我错误地提到了DFS的时间复杂度，dfb所说的最有可能是正确的，因为O（m * n + n + m）是DFS的时间复杂度，所以最终的复杂度将是 O（n * m * n + n * n + n * m）= O（m * n^2） – ksm001 2013-03-10 19:42:45

变量在这里有点令人困惑：M和N指的是图形每一边的节点数量。 DFS的运行时间是O(E+V)其中E是边的数量。在二部图| E |中最多N * M，V将是（N + M），因此您的DFS将采取O(NM)。总时间复杂度为O(NM^2)。不知道N^2进来的地方，可能是一个错字...

来源

2013-03-10 19:32:59 dfb

谢谢，我有点困惑随着DFS时间的复杂性，你的解释对我来说很有意义。 – ksm001 2013-03-10 19:43:17

为什么以下最大二部匹配实现O（m * n^2）的时间复杂度？

回答

相关问题