La complexité du 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 graphique. Voici le code. Mais je ne sais pas comment la complexité de calcul en elle à cause de la méthode récursive au milieu. Depuis 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 déterminer réellement?

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 fois longestPath de m, et il y a une boucle qui exécute les temps de test n visité). Le scénario de base est T(n, 0) = O(n) (juste le test visité).

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