2

例如，如果输入字符串是“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;
}

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

4

2 回答 2

4

如果你让 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，
  • ...
  • 嗯！/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!)。

希望这可以帮助！

于 2013-10-11T20:33:14.380 回答
1

运行您的代码并根据要置换的字符串的长度列出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！”。

于 2013-10-11T09:06:46.307 回答