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

Question

例如，如果输入字符串是“ABC”，那么输出应该是“ABC、ACB、BAC、BCA、CAB、CBA”。

这是我的方法:

#include<stdio.h>
#include<conio.h>
#include<string.h>

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

所以总调用次数由总和给出

sum from k = 0 to n (n! / k!)

= n! (sum from k = 0 to n (1 / k!))

一个有趣的观察是这里的总和是 e 的泰勒展开式 (1/0! + 1/1! + 1/2! + 1/3! + ... )，提前截断了一点。因此，随着 n 变大，调用次数逐渐接近 en!。它的下界也是 n!，所以这个总和是 Θ(n!)。由于您每次调用完成了 Θ(n) 项工作，因此完成的总工作量为 Θ(n · n!)。

希望这对您有所帮助!