0

次の時間と空間の複雑さは何ですか:

int superFactorial4(int n, int m)
{
    if(n <= 1)
    {
        if(m <= 1)
            return 1;
        else 
            n = m -= 1;
    }

    return n*superFactorial4(n-1, m);
}

n の値が 1 になるまで n の値を 1 ずつ減らして再帰的に実行され、m の値を 1 減らすか、m が 1 の場合は 1 を返します。

複雑さはnとmの両方に依存すると思うので、おそらくO（n * m）です。

4

3 に答える 3

3

時間の複雑さはO(n+m^2)、空間の複雑さは同じです。

理由: の固定値を使用するmと、関数はnそれ自体に再帰呼び出しを行い、それぞれが一定の作業を行うため、固定値を使用した呼び出しの複雑さmは ですn。さて、n が 0 になるm-1と、それもまたmなるm-1。したがって、次の固定 m フェーズはm-1、次m-2などになります。したがって、合計(m-1)+(m-2)+...+1は になりO(m^2)ます。

再帰呼び出しごとに、再帰は一定のスペースを使用し、最後を除いて再帰から戻ることはなく、末尾再帰がないため、スペースの複雑さは同じです。

于 2009-02-10T11:32:49.770 に答える
3

実際には、私には O(N+m^2) に近いように見えます。n は最初の「サイクル」にのみ使用されます。

また、テールコールの最適化を行わない言語では、スペースの複雑さは「失敗」する可能性があります。最適化をサポートする言語では、スペースの複雑さは O(1) に似ています。

于 2009-02-10T11:33:27.893 に答える
-1

再帰疑似コードを使用した階乗関数の時間計算量:

int fact(n)
{ 
   if(n==0)
   { 
      return 1;
   }
   else if(n==1)
   {
        return 1;
   }
   else if
   {
      return n*f(n-1);
   }
}

time complexity;     
let T(n) be the number of steps taken to compute fact(n).


we know in each step F(n)= n*F(n-1)+C

F(n-1)= (n-1)*F(n-2)+c

substitute this in F(n), we get

F(n)= n*(n-1)*F(n-2)+(n+1)c

大きな o 表記を使用すると、次のように言えます。

F(n)>= n*F(n-1)
F(n)>= n*(n-1)*F(n-2)
.
.
.
.
.
F(n)>=n!F(n-k)

T(n)>=n!T(n-k)

n-k=1;
k=n-1;

T(n)>=n!T(n-(n-1))
T(n)>=n!T(1)
since T(1)=1
T(n)>=1*n!

今、それはの形になっています

 F(n)>=c(g(n))

したがって、再帰を使用した階乗の時間計算量は 

T(n)= O(n!)
于 2011-09-23T14:42:06.690 に答える