재귀 적 방법을 사용한 최장 경로 알고리즘의 연산 복잡도

Question

코드 세그먼트를 작성하여 그래프에서 가장 긴 경로를 결정했습니다. 다음은 코드입니다. 하지만 중간에 재귀 적 방법이 있기 때문에 계산상의 복잡성을 얻는 방법을 모르겠습니다. 가장 긴 경로를 찾는 것이 NP 완료된 문제이므로 O(n!) 또는 O(2^n)과 같지만 실제로 어떻게 결정할 수 있습니까? n 노드의 수를 나타내며, m이 방문하지 않은 노드의 수를 나타낸다 (당신이 longestPathm 번 호출하기 때문에, 그리고 방문 테스트 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)입니다. 기본 경우는 T(n, 0) = O(n) (방금 방문한 테스트)입니다.

이것을 풀면 T (n, n)이 O (n * n!)가된다고 생각합니다.

편집

작업 :

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