我编写了一个代码段来确定图中的最长路径。以下是代码。但是由于中间的递归方法,我不知道如何获得其中的计算复杂度。由于找到最长的路径是一个 NP 完全问题,我认为它类似于O(n!)
or 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);
}