algorithm - 使用 DP 的 Tsp 时间复杂度

Question

这是问题的递归公式：

C(i,S) = min { d(i,j) + C(j,S-{j}) }

实际上，当我尝试将其实现为代码时，我想到了以下代码：

int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j++)
     {
      cost = dist(i,S[j])+TSP(j,S-{j});
      if(cost < min)
       min = cost;
      }
global_cost+=min;
return min;
}

因为这for会比较 n 次以找到最小值，这意味着它的递归为：

T(n) = nT(n-1)+n ==> T(n) = O(n!)

因为我们比较每个步骤以找到大小 S 的最小大小，当然，代码是阶乘的。那么它与子集有什么关系，那么为什么时间的复杂性是(n^2*2^n)？它的时间复杂度的证明是什么？

标签： algorithmtime-complexitytraveling-salesman