2

私はこの特定の複雑さの計算に頭を悩ませようとしてきましたが、このタイプの複雑さについて読んだことはすべて、それが大きな O(2^n) 型であると言っていますが、コードにカウンターを追加していくつあるかを確認すると指定された n ごとに反復する回数は、代わりに 4^n の曲線に従うようです。count++; を配置したときに誤解しただけかもしれません。範囲内。

これは大きな O(2^n) 型ではありませんか? 

   public int test(int n) 
   {    
   if (n == 0)
   return 0;
   else
   return test(n-1) + test(n-1);
    }

これに関するヒントや説明をいただければ幸いです。私はこの複雑さの計算に完全に不慣れで、これは私を軌道から外しました。

//よろしく

4

4 に答える 4

4 
int test(int n)
{
    printf("%d\n", n);

    if (n == 0) {
        return 0;
    }
    else {
        return test(n - 1) + test(n - 1);
    }
}

関数の先頭に出力を付けて実行test(8)し、それぞれが出力された回数をカウントすると、nこの出力が得られます。これは明らかに 2 nの成長を示しています。

$ ./test | sort | uniq -c
    256 0
    128 1
     64 2
     32 3
     16 4
      8 5
      4 6
      2 7
      1 8

(uniq -cは各行の出現回数をカウントします0。256 回、1128 回などと表示されます)

おそらく、O(4 n )ではなく、 O(2 n +1 ) という結果が得られたということでしょうか? これらの数をすべて足すと、511 になります。これは、n =8 の場合、2 n +1 -1 です。

それがあなたの言いたいことなら、それでいいのです。O(2 n +1 ) = O(2⋅2 n ) = O(2 n )

于 2013-04-16T20:35:41.777 に答える
1

まず、「else」ステートメントは廃止されました。if が true と評価された場合は既に返されるためです。

トピックについて: すべての反復は 2 つの異なる反復をフォークし、2 つの反復自体をフォークします。そのため、n=1 の場合、関数は 2 回呼び出され、さらに元の呼び出しが行われます。n=2 の場合、4+1 回、次に 8+1、次に 16+1 などと呼ばれます。定数が指数関数によって相殺されるため、複雑さは明らかに 2^n です。

コール間でカウンターが適切にリセットされなかったと思われます。

于 2013-04-16T20:39:59.703 に答える
1

x(n) を の合計呼び出し数としtestます。

x(0) = 1

x(n) = 2 * x(n - 1) = 2 * 2 * x(n-2) = 2 * 2 * ... * 2

n 2 の合計があるため、2^n 呼び出しです。

于 2013-04-16T20:36:13.783 に答える
1

この関数の複雑さT(n)は、 に等しいことを簡単に示すことができますc + 2*T(n-1)。によって与えられる再帰

T(0) = 0
T(n) = c + 2*T(n-1)

解として c*(2^n - 1) などがあります。O(2^n)です。

さて、m = lg nこのシナリオで許容されるように、関数の入力サイズnをO(m^4)^2) = O(m^4)。

于 2013-04-16T20:43:45.117 に答える