用递归方法计算最长路径算法的复杂度

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！）。

编辑

工作：

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