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

私の答えは方法論に焦点を当てるつもりです。それが明示的な質問の目的だからです。この特定の問題に対する回答については、amit などの他の回答を参照してください。

再帰を使用してアルゴリズムの複雑さを評価しようとしている場合は、反復アルゴリズムの場合と同じようにカウントを開始する必要があります。ただし、再帰呼び出しが発生した場合、正確なコストはまだわかりません。行のコストを関数として記述し、実行回数を数えるだけです。

例（このコードはばかげていることに注意してください。これは例としてここにあるだけで、意味のあることは何もしていません-要点を維持している限り、自由に編集してより良いものに置き換えてください）：

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 の文字列の場合)

  • start : N p. 各N-1 pから始めます。等...
  • 順列の数は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 に答える