complessità computazionale di un algoritmo di percorso più lungo con un metodo ricorsivo

Question

ho scritto un segmento di codice per determinare il percorso più lungo in un grafico. Di seguito è riportato il codice. Ma io non so come ottenere la complessità computazionale in esso a causa del metodo ricorsivo nel mezzo. Dal momento che trovare il percorso più lungo è un problema NP completo Penso che sia qualcosa di simile O(n!) o O(2^n), ma come posso davvero determinarlo?

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

La vostra relazione di ricorrenza è T(n, m) = mT(n, m-1) + O(n), dove n denota numero di nodi e m denota numero di nodi non visitati (perché si chiama volte longestPath m, e non v'è un ciclo che esegue i tempi di test n visitati). Il caso base è T(n, 0) = O(n) (solo il test visitato).

Risolvere questo e credo che si ottiene T (n, n) è O (n * n!).

Modifica

di funzionamento:

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