Вычислительная сложность алгоритма самого длинного пути с рекурсивным методом

Question

Я написал сегмент кода, чтобы определить самый длинный путь в графе. Ниже приведен код. Но я не знаю, как вычислить сложность в нем из-за рекурсивного метода в середине. Поскольку найти самый длинный путь - это полная NP проблема, я предполагаю, что это что-то вроде O(n!) или O(2^n), но как я могу это определить?

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

Ваше рекуррентное соотношение является T(n, m) = mT(n, m-1) + O(n), где n обозначает число узлов и m обозначает количество непосещенных узлов (потому что вы называете longestPathm раз, и есть цикл, который выполняет гостевой тест n раз). Основной корпус - T(n, 0) = O(n) (только что посетивший тест).

Решите это, и я верю, что вы получаете T (n, n) O (n * n!).

EDIT

Рабочая:

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