performance - 为什么下面的最大二分匹配实现的时间复杂度是O(m*n^2)？

Question

这个库实现了许多算法，其中之一是最大二分匹配。

这是源代码的链接: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 次的 for 循环。数字 m 指的是 worker 的数量。然后我们进入有另一个 for 循环的 bpm 函数。此循环运行 n 次，其中 n 是任务的数量。

到目前为止，我们的时间复杂度为 m*n。

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

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

因此总时间复杂度为O(m*(n+m))

然而作者说它是O(m*n^2)。有人可以向我解释为什么会这样吗？提前致谢!

Answer 1

变量在这里有些困惑:M 和 N 指的是图每边的节点数。 DFS 的运行时间是 O(E+V)，其中 E 是边数。在二分图中 |E|最多为 N*M，V 将为 (N+M)，因此您的 DFS 将采用 O(NM)。总时间复杂度为 O(NM^2)。不确定 N^2 的来源，可能是打字错误...