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) であるため、行われた呼び出しの合計数を見ることで、行われた作業の合計を数えることができます。

があることに注意してください

  • k = n で 1 回の呼び出し、
  • k = n - 1 の n 回の呼び出し、
  • k = n - 2 の n(n-1) 回の呼び出し、
  • n(n-1)(n-2) 回の呼び出し (k = n - 3)、
  • ...
  • ん！/k！任意の k を呼び出す

したがって、呼び出しの総数は合計で与えられます

k = 0 から n までの合計 (n! / k!)

=ん！(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 に答える