2

多くのアルゴリズムが実装されているこのライブラリがあり、そのうちの1つは最大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;
}

実行時間のforループがありますm。数字mは労働者の数を表しています。次に、bpm別のforループを持つ関数に入ります。このループは、タスクの量であるn回数を実行します。n

今まではm*n時間計算量がありました。

bpmただし、3番目のifステートメントにはの再帰関数呼び出しがあります。この関数の目的はdfs、拡張パスを見つけるためにを実行することです。

私はそれdfsが時間の複雑さを持っていることを知っていますO(n+m)。したがって、関数bpmの複雑さは次のようになります。O(n+m)

したがって、合計時間計算量は次のようになります。O(m*(n+m))

しかし、作者はそれがだと言いますO(m*n^2)。誰かが私にこれが事実である理由を説明できますか？前もって感謝します！

4

1 に答える 1

3

ここでは、変数がやや混乱しています。MとNは、グラフの両側にあるノードの数を表します。DFSの実行時間はO(E+V)、Eがエッジの数である場合です。2部グラフ|E| は最大でN*Mであり、Vは（N + M）になるため、DFSはを取りO(NM)ます。その場合、合計時間計算量はO(NM^2)です。どこにN^2入るのかわからない、タイプミスの可能性があります...

于 2013-03-10T19:32:59.337 に答える