6

我编写了一个代码段来确定图中的最长路径。以下是代码。但是由于中间的递归方法,我不知道如何获得其中的计算复杂度。由于找到最长的路径是一个 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);
}
4

1 回答 1

8

您的递归关系是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!)
于 2010-12-14T10:40:54.870 回答