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

Question

我曾使用过这个程序，如何计算回溯算法的时间复杂度？

/*
  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
    }
  }
}

- user1213495

Answer 1

每个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! 编辑：[小修正]：由于循环语句中的条件为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)!。
然而，这似乎更像是实现上的错误而不是特性 :\

- amit

---

作为旁注，由于有n!个n个对象的排列，如果OP的算法具有其他复杂度，那将是一个相当大的惊喜。 - Victor Sorokin

Answer 2

一个简单的想法是，会有n！种排列方式，你必须将它们全部生成。因此，你的时间复杂度至少为n！，因为你必须遍历所有n！才能生成它们。 因此，时间复杂度为O(n!)。

- Chee Loong Soon