我编写了一个代码段来确定图中的最长路径。以下是代码。但由于中间的递归方法,我不知道如何获得其中的计算复杂度。由于找到最长的路径是一个 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);
}
你的递归关系是T(n, m) = mT(n, m-1) + O(n)
, where n
表示节点数,m
表示未访问节点的数量(因为您调用longestPath
m
次,并且有一个循环执行访问的测试n
次)。基本情况是T(n, 0) = O(n)
(只是访问过的测试)。
解决这个问题,我相信你会得到 T(n, n) 是 O(n * n!)。
EDIT
Working:
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!)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)