列出所有排列的代码的时间复杂度？

例如，如果输入字符串是“ABC”，则输出应为“ABC，ACB，BAC，BCA，CAB，CBA”。

这是我的方法：

#include #include #include void print(char str[],int visited[],int index,char temp[],int len) { if(index==len) { temp[index]='\0'; printf("\n%s",temp); return; } for(int i=0;i<len;i++) { if(!visited[str[i]-'A']) { visited[str[i]-'A']=1; temp[index]=str[i]; print(str,visited,index+1,temp,len); visited[str[i]-'A']=0; } } } int main() { int visited[20]={0}; char temp[20]; char str[] = "ABCD"; int len=strlen(str); print(str,visited,0,temp,len); getch(); return 0; } 

我已经使用了一个访问过的数组来避免重复字符。 这段代码的复杂性是什么？

Answer 1

如果你让n是可用的字符总数而k是未选择的字符数，那么你可以看到每个函数调用都做Θ（n）工作（通过迭代长度len的数组或通过打印输出一个长度为len的字符串，然后产生k个递归调用。 每次通话完成的总工作总是Θ（n），因此我们可以通过查看完成的总呼叫数来计算完成的总工作量。

请注意，会有

• 1次呼叫，k = n，
• n次调用k = n – 1，
• n（n-1）次调用k = n – 2，
• n（n-1）（n-2）次调用k = n – 3，
• …
• N！ / k！ 要求任意k

所以总呼叫数由总和给出

从k = 0到n的总和（n！/ k！）

= n！ （从k = 0到n（1 / k！）之和）

一个有趣的观察结果是，这里的求和是e（1/0！+ 1/1！+ 1/2！+ 1/3！+ …）的泰勒展开，稍早截断。 因此，当n变大时，渐进的调用次数接近en！。 它也受到n！的下限，所以这个总和是Θ（n！）。 由于每次调用都完成了Θ（n）工作，因此完成的工作总量为Θ（n·n！） 。

希望这可以帮助！

Answer 2

运行你的代码并列出print()调用的数量，具体取决于要置换的字符串的长度，我得到：

 n=1 calls=2 n=2 calls=5 n=3 calls=16 n=4 calls=65 n=5 calls=326 n=6 calls=1957 n=7 calls=13700 n=8 calls=109601 n=9 calls=986410 n=10 calls=9864101 n=11 calls=108505112 

看起来像“e * n！”。