具有递归方法的最长路径算法的计算复杂度
我编写了一个代码段来确定图中最长的路径。以下是代码。但由于中间的递归方法，我不知道如何在其中获得计算复杂性。由于找到最长的路径是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);
}
没有找到相关结果
已邀请:
1 个回复
细瑞
，其中表示节点数，表示未访问节点的数量（因为你调用次，并且有一个循环执行访问测试次）。基本情况是（只是访问过的测试）。 解决这个，我相信你得到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!)