最も長いパスアルゴリズムの計算の複雑さは、再帰的な方法になります

Question

グラフで最長のパスを決定するためにコードセグメントを書きました。以下はコードです。しかし、中央に再帰的な方法があるため、計算の複雑さをどのように取得するかわかりません。最長のパスを見つけることはNP完全な問題であるため、私はそれが次のようだと思います O(n!) また O(2^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), 、 どこ n ノードの数を示します m 訪問されていないノードの数を示します（呼び出すため longestPath m 時間、そして訪問されたテストを実行するループがあります n 時間）。基本ケースはです T(n, 0) = O(n) （訪問したテストだけ）。

これを解決すると、t（n、n）がO（n * n！）を取得すると思います。

編集

働く：

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!)