Berechnungskomplexität eines Algorithmus für den längsten Pfad mit einer rekursiven Methode

Question

Ich habe ein Codesegment geschrieben, um den längsten Pfad in einem Diagramm zu bestimmen. Folgendes ist der Code. Aber ich weiß nicht, wie ich die rechenintensive Methode durch die rekursive Methode in der Mitte erreichen kann. Da das Finden des längsten Pfades ein NP-vollständiges Problem ist, nehme ich an, dass es etwas wie O(n!) oder O(2^n) ist, aber wie kann ich es tatsächlich feststellen?

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 Anzahl der Knoten bezeichnet und m bezeichnet Anzahl von unvisited Knoten (weil Sie longestPathm mal nennen, und es ist eine Schleife, die die besuchten Test n mal ausführt). Der Basisfall ist T(n, 0) = O(n) (nur der besuchte Test).

Lösen Sie dies und ich glaube, Sie bekommen T (n, n) ist O (n * n!).

EDIT

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