Rechenkomplexität eines längsten Pfad-Algorithmus mit einer rekursiven Methode

Question

schrieb ich ein Codesegment des längsten Weg in einem Graphen zu bestimmen. Im Folgenden finden Sie den Code ein. Aber ich weiß nicht, wie in den Rechenaufwand zu erhalten, weil die rekursiven Methode in der Mitte. Seit dem längsten Weg zu finden, ein NP vollständiges Problem ist gehe ich davon aus, es ist etwas wie O(n!) oder O(2^n), aber wie kann ich es tatsächlich bestimmen?

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

Ihre Rekursion ist T(n, m) = mT(n, m-1) + O(n), wo n bezeichnet Anzahl von Knoten und m Anzahl der noch nicht besuchten Knoten bezeichnet (weil Sie longestPath m mal nennen, und es gibt eine Schleife, die die besuchten Test n mal ausführt). Der Basisfall ist T(n, 0) = O(n) (nur der besuchten Test).

Lösen Sie dieses und ich glaube, Sie T erhalten (n, n) O (n * n!).

Bearbeiten

Arbeits:

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