Complexité de calcul d'un algorithme de chemin le plus long avec une méthode récursive

Question

J'ai écrit un segment de code pour déterminer le chemin le plus long dans un graphe. Voici le code. Mais je ne sais pas comment obtenir la complexité de calcul en raison de la méthode récursive au milieu. Puisque trouver le chemin le plus long est un problème NP complet je suppose que c'est quelque chose comme O(n!) ou O(2^n), mais comment puis-je réellement le déterminer?

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

Votre relation de récurrence est T(n, m) = mT(n, m-1) + O(n), où n représente nombre de noeuds et m représente nombre de noeuds non visités (parce que vous appelez longestPathm fois, et il y a une boucle qui exécute le test visité n fois). Le cas de base est T(n, 0) = O(n) (juste le test visité). Résoudre cette question et je crois que vous obtenez T (n, n) est O (n * n!).

EDIT

travail:

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