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

本文介绍了最长路径算法与递归方法的计算复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我写了一个代码段来确定图中的最长路径.以下是代码.但是由于中间有递归方法，我不知道如何获得计算复杂性.由于找到最长的路径是一个NP完整问题，因此我假设它类似于O(n!)或O(2^n)，但是我该如何确定呢?

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

推荐答案

您的重复关系为T(n, m) = mT(n, m-1) + O(n)，其中n表示节点数，而m表示未访问节点数(因为您调用longestPath m次，并且有一个循环执行访问的测试n次).基本情况是T(n, 0) = O(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).

解决这个问题，我相信您得到的T(n，n)是O(n * n！).

Solve this and I believe you get T(n, n) is 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 oeis/A000522) = O(n*n!)