2

この特定のコードの Theta ランタイムを計算するにはどうすればよいですか。

void f(int n)
{
    for (int i=3; i<n; ++i)
        for (int j=0; j<i; ++j)
            f(n-1);
}

これまでのところ私はこれを得ましたが、それが正しいかどうか、またはシータ表記でそれをどのように持ってくるかはわかりません。

f(n) = n^2 * f(n-1)
f(n) = n^2 * (n-1)^2 * f(n-2)
f(n) = n^2 * (n-1)^2 * (n-2)^2 * f(n-3) 
...
4

2 に答える 2

2

ネストされた各 for ループは O(N^2) の複雑さであり、別の関数内で関数を呼び出すたびに複雑さが増し、O((N!)^2) にNなります。再帰する回数。これはもちろんN! = N*(N-1)*(N-2)*...*(N-N+1)、階乗を作成するために使用されるすべての値が 2 乗されているためです。

于 2012-06-07T12:26:16.897 に答える
1

その 3 をゼロに置き換えると (明らかに Θ については何も変化しません)、関数呼び出しの正確な量を非常に簡単に導き出すことができます。

Θ f ( 1 ) = 1
Θ f ( n ) = n 2 ⋅ Θ f ( n -1 )         ∀ n > 0

したがって、積の可換性を使用して、

                  n                  <sub> n           n
Θ f ( n ) = ∏   j 2   = ∏ j   ⋅ ∏ j   =  n ! ⋅ン！
               <em>i =1 <em>i =1 <em>i =1
= ( n !) 2

ジェイソンが言ったように。

于 2012-06-07T13:19:42.903 に答える