Tính phức tạp tính toán của một thuật toán đường dẫn dài nhất witn một phương pháp đệ quy

Question

Tôi đã viết một đoạn mã để xác định đường đi dài nhất trong biểu đồ. Sau đây là mã. Nhưng tôi không biết làm thế nào để có được sự phức tạp tính toán trong nó vì phương pháp đệ quy ở giữa. Vì việc tìm con đường dài nhất là một vấn đề hoàn chỉnh NP, tôi cho rằng đó là một cái gì đó như O(n!) hoặc O(2^n), nhưng làm cách nào để tôi có thể xác định 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

quan tái phát của bạn là T(n, m) = mT(n, m-1) + O(n), nơi n biểu thị số nút và m biểu thị số nút unvisited (vì bạn gọi longestPathm lần, và có một vòng lặp mà thực hiện các thử nghiệm thăm n lần). Vỏ cơ sở là T(n, 0) = O(n) (chỉ là bài kiểm tra được truy cập).

Giải quyết vấn đề này và tôi tin rằng bạn nhận được T (n, n) là O (n * n!).

EDIT

làm việc:

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