用递归方法计算最长路径算法的复杂度

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

链接地址: http://www.djcxy.com/p/6693.html

上一篇: Computational complexity of a longest path algorithm witn a recursive method

下一篇: QDialog focus without window manager