最长路径算法的计算复杂性
-
09-10-2019 - |
题
我编写了一个代码段,以确定图中最长的路径。以下是代码。但是我不知道如何获得计算复杂性,因为中间有递归方法。由于找到最长的路径是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);
}
解决方案
您的复发关系是 T(n, m) = mT(n, m-1) + O(n)
, , 在哪里 n
表示节点的数量和 m
表示未访问的节点的数量(因为您致电 longestPath
m
时间,还有一个循环执行访问的测试 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!)
不隶属于 StackOverflow