3

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

# 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 2 )。如何检查递归情况下的时间复杂度？如果我错了，请纠正我。

谢谢。

4

3 回答 3

3

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

于 2013-01-16T07:05:31.563 回答
2

我的回答将集中在方法论上，因为这是明确的问题。有关此特定问题的答案，请参阅其他人的答案，例如阿米特的。

当您尝试使用递归评估算法的复杂性时，您应该像使用迭代算法一样开始计数。但是，当您遇到递归调用时，您还不知道确切的成本是多少。只需将行的成本写为函数，然后仍然计算它将运行的次数。

例如（请注意，此代码是愚蠢的，它只是为了示例而在这里，并没有做任何有意义的事情 - 只要它保持要点，随意编辑并用更好的东西替换它）：

int f(int n){ //Note total cost as C(n)
  if(n==1) return 0; //Runs once, constant cost
  int i;
  int result = 0; //Runs once, constant cost
  for(i=0;i<n;i++){
    int j;
    result += i; //Runs n times, constant cost
    for(j=0;j<n;j++){
      result+=i*j; //Runs n^2 times, constant cost
    }
  }
  result+= f(n/2); //Runs once, cost C(n/2)
  return result;
}

把它加起来，你会得到一个递归公式，比如C(n) = n^2 + n + 1 + C(n/2)and C(1) = 1。下一步是尝试将其更改为通过直接表达式对其进行绑定。从那里根据您的公式，您可以应用许多不同的数学技巧。

对于我们的示例：

对于n>=2：C(n) <= 2n^2 + C(n/2)

由于 C 是单调的，让我们考虑C'(p)= C(2^p)： C'(p)<= 2*2^2p + C'(p-1)

这是一个典型的求和表达式（这里不方便写，所以我们跳到下一步），我们可以绑定：C'(p)<=2p*2^2p + C'(0)

回过头来C(n)<=2*log(n)*n^2 + C(1)

因此运行时在O(log n * n^2)

于 2013-01-16T11:06:17.800 回答
1

通过这个程序的确切排列数是（对于长度为 N 的字符串）

  • 开始：N p。开始每个 N-1 p。ETC...
  • 排列数是N + N(N-1) + N(N-1)(N-2) + ... + N(N-1)...(2)（以 2 结尾，因为下一个调用刚刚返回）
  • 或者N(1+(N-1)(1+(N-2)(1+(N-3)(1+...3(1+2)...))))

大致是哪个2N!

在for循环中添加计数器（删除 printf）与公式匹配

  • N=3 : 9
  • N=4 : 40
  • N=5 : 205
  • N=6 : 1236 ...

时间复杂度为O(N!)

于 2013-01-16T12:06:13.503 回答