再帰的メソッドと最長のパスアルゴリズムの計算複雑度

Question

グラフの中で最も長いパスを決定するコードセグメントを書きました。以下はコードです。しかし、私は途中の再帰的な方法のために計算上の複雑さをどのように得るのか分かりません。最長の経路を見つけることはNP完全な問題であるので、それはO(n!)またはO(2^n)のようなものだと仮定しますが、どうすれば実際にそれを決定できますか？ nは、ノードの数を示し、mは未訪問のノードの数を表し、（あなたがlongestPathm回呼び出すため、および訪問したテストn回実行するループがある）ところ

public static int longestPath(int A) { 
    int k; 
    int dist2=0; 
    int max=0; 

    visited[A] = true; 

    for (k = 1; k <= V; ++k) { 
     if(!visited[k]){ 
      dist2= length[A][k]+longestPath(k); 
      if(dist2>max){ 
       max=dist2; 
      } 
     } 
    } 
    visited[A]=false; 
    return(max); 
} 

Answer 1

あなたの漸化式は、T(n, m) = mT(n, m-1) + O(n)です。基本ケースはT(n, 0) = O(n)（訪問したテストのみ）です。

これを解くと、T（n、n）がO（n * n！）になると思います。

EDIT

ワーキング：

T(n, n) = nT(n, n-1) + O(n) 
     = n((n-1)T(n, n-2) + O(n)) + O(n) = ... 
     = n(n-1)...1T(n, 0) + O(n)(1 + n + n(n-1) + ... + n(n-1)...2) 
     = O(n)(1 + n + n(n-1) + ... + n!) 
     = O(n)O(n!) (see http://oeis.org/A000522) 
     = O(n*n!)