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

发布于 2024-10-08 04:17:06 字数 511 浏览 0 评论 0原文

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

原文

I wrote a code segment to determine the longest path in a graph. Following is the code. But I don't know how to get the computational complexity in it because of the recursive method in the middle. Since finding the longest path is an NP complete problem I assume it's something like O(n!) or O(2^n), but how can I actually determine it?

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);
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

情域 2024-10-15 04:17:06

您的递归关系为 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!)

Your recurrence relation is T(n, m) = mT(n, m-1) + O(n), where n denotes number of nodes and m denotes number of unvisited nodes (because you call longestPath m times, and there is a loop which executes the visited test n times). The base case is T(n, 0) = O(n) (just the visited test).

Solve this and I believe you get T(n, n) is 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!)

回复收藏 0 原文

~没有更多了~