c - 如何计算回溯算法的时间复杂度

使用了这个程序，如何计算回溯ALGO的时间复杂度？

/*
  Function to print permutations of string    This function takes three parameters:
  1. String
  2. Starting index of the string
  3. Ending index of the string.
*/
void swap (char *x, char *y)
{
  char temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

void permute(char *a, int i, int n)
{
  int j;

  if (i == n)
    printf("%s\n", a);
  else
  {
    for (j = i; j <= n; j++)
    {
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
    }
  }
}

最佳答案

每个permute(a,i,n)都会导致n-i调用permute(a,i+1,n)
因此，当i == 0存在n调用时，当i == 1存在n-1调用时…当i == n-1有一个呼叫时。
从中可以找到迭代次数的递归公式：
T(1) = 1[基本]；和T(n) = n * T(n-1)[步骤]
总计T(n) = n * T(n-1) = n * (n-1) * T(n-2) = .... = n * (n-1) * ... * 1 = n!
编辑：[小修正]：由于for循环中的条件是j <= n[而不是j < n]，因此每个permute()实际上都在调用n-i+1次permute(a,i+1,n)，导致t（n）=(n+1) * T(n-1)[步骤]和T(0) = 1[基]，这将导致T(n) = (n+1) * n * ... * 1 = (n+1)!。
然而，这似乎是一个实现缺陷，而不是一个特性：\