0

誰かがnビット文字列（すべての可能な組み合わせ）を生成する方法を教えてもらえますか？つまり、分割統治法を使用して0から2^n-1までのビットを数えます。

次のアルゴリズムでこれを行うことができましたが、空間の複雑さと時間の複雑さはO（2 ^ n）です。誰かが私に（分割統治法を使用して）これよりも少ないスペースを必要とするより良いアルゴリズムを教えてもらえますか？

ArrayList generate(int n)
 {
      if(n==1) 
         {  
            Create an arrayList and store strings "0" and "1";
         }
     else
    {
         generate(n-1)

         now recompose the solution to get 2^n strings and return this arraylist
         "PROBLEM here is that the length of the array list is also getting
         exponential"

    }
 }
4

1 に答える 1

0

あなたは誤解されていると思います。ビット文字列の生成自体は問題ではないため、解決策を提案することはできません。おそらくあなたは問題の一部を省略しました。たとえば、ビット文字列を使用してソリューションの表現を定義してから、特定の問題に最適なビット文字列を見つけようとする場合があります。

もう1つ、一般に、nビット文字列として表される問題の時間計算量は、問題が定義されていない限り、常にO（2 ^ n）です。次に、問題の基準を使用して、どちらかの複雑さを軽減できます。しかし、問題が定義される前に、nビット文字列を生成してトラバースするには、常に、考えられるすべての2^nの組み合わせに注意を払う必要があります。

編集：

必要に応じて、分割統治法の擬似コードを次に示します。

solution breakdown(problem p)
{
    if (smallenough(p))
    {
        return solve(p);
    }
    problem[] subproblems = divide(p);
    solution[] subsolutions;
    for (i=0; i<count(subproblems); i++)
    {
        subsolutions[i] = breakdown(subproblems[i]);
    }
    return reconstruct(subsolutions);
}
于 2012-09-17T05:43:08.870 に答える