c - c中的递归顺序

Question

我编写了一个程序，使用回溯法打印字符串的所有排列。

# include <stdio.h>
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

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

/* Driver program to test above functions */
int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

这里的时间复杂度是多少，不就是o(n²)吗。递归的情况下如何判断时间复杂度呢？如果我错了，请纠正我。

谢谢。

Answer 1

复杂度是O(N*N!)，你有N!排列，你得到所有的排列。
此外，每个排列都需要您打印它，这是 O(N) - 所以总计 O(N*N!)