algorithm - for循环中递归的复杂性

Question

我试图分析这个算法的复杂性，我预测它是 t(n) = n*t(n) + 1 并解决了 t(n) 通过主定理，即 n^logn。但是，我不确定，并坚持下去。

  Algorithm CheckPath(m[0..n-1][0..n-1],v1,v2)
       if v1==v2
       return 0
   cost = 0
   for i = 0 to n-1
     if  m[v1]m[v2]!=0 //any path exits
       cost2 = m[v1]m[v2]+checkpath(m,i,v2)
       if cost2<cost OR cost==0
         cost = cost2
return cost

编辑:我将 costtmp 更正为成本 2，当我检查 v1==v2 是否返回 0

时它不会进入无限循环

Answer 1

我认为你的做法是错误的。你有一个算法，它运行在一些图上。因此，请尝试在底层图形上而不是在您运行的递归上找到它的复杂性。

但是要回答您最初的问题，您的递归具有指数复杂度(并且可能不会终止)，除非您的图是 DAG(有向无环图)。这样做的原因是因为您没有将已经到达的顶点标记为这样。因此，递归可以在两个顶点 u 和 v 之间无限循环，这样边 (u, v) 和 (v, u) 在 E 中(或者简单地说，如果你的图是无向的，那么任何边都会导致这种情况)。