0

私はコードを解決していて、再帰関数は次のようになりました->

int rec(n)
{

  if(n>=(n/2+n/3+n/4))
  {
      return n;
  }


  else
  {

     return  rec(n/2) + rec(n/3) + rec(n/4); 

  }

}

この関数の時間の複雑さはどうなるのだろうと思っていましたか?

再帰関係は次のようになると思います-

T(n) = T(n/2) + T(n/3) + T(n/4) + f(n)

この再帰関係をどのように解決しますか? この場合、f(n) の値はどうなるでしょうか?

また、これを動的計画法に変換するにはどうすればよいでしょうか?

これを動的に変換するために私が書いたコードは-

    long long  rec(long long n)
{
    long long c[n]; // The number range is between 1 to 10^9


    for(int i=0;i<n;i++)
    c[n]=0;


    if(n>=(n/2+n/3+n/4))
    {
        c[n]=n;
        return n;
    }
    else
    {
        if (c[n]==0)
        c[n]=c[n/2]+c[n/3]+c[n/4];
        return c[n];
    }

}

ただし、再帰を動的に変換した後、私のプログラムは正しい答えを表示することを拒否します。IIはそれを動的計画法に適切に変換していないと思います。それを行う方法を教えてください。

ありがとう

4

1 に答える 1

1

if (n >= (n/2 + n/3 + n/4)) は基本的に if (n <= 0) と同等です。n は 0 未満にはならないので、 if (n == 0) return n; と書いても問題ありません。これは、時間計算量が次の漸化式によって与えられることを意味します。

T(0) = 1
T(n) = T(n/2) + T(n/3) + T(n/4)

小さな問題での問題の分割は対称的ではないため (そして、n/2 + n/3 + n/4 = 13n/12 であり、n よりも大きいため)、最初の近似 (大きなもの) では、O の間で言います。 (nlogn) と O(n^2)。O(nlog2n) であることを証明しようとしましたが、チェックアウトしませんでした (log2n とは、n の基数 2 でログインすることを意味します):

T(n) <= cnlog2n

これからは logn だけ書きます

T(n) <= cn/2*logn/2 + cn/3*logn/3 + cn/4*logn/4
      = cn/2*logn - cn/2*log2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/4*log4
      = cn/2*logn - cn/2 + cn/3*logn - cn/3*log3 + cn/4*logn - cn/2
      = 13/12*cn*logn - cn(log3/3 - 1)

cnlogn 以下ではない

O(n^2) は、次のように真であることを証明できます。

if T(n) = O(n^2) then T(n) <= cn^2
T(n) <= c(n/2)^2 + c(n/3)^2 + c(n/4)^2
      = cn^2/4 + cn^2/9 + cn^2/16
      = 15cn^2/36 <= cn^2

したがって、O(n^2) 仮説は真ですが、あまり正確ではない可能性があります。O(nlogn) と O(n^2) の間で別の仮説を試して、上記のようにそれらが真であるかどうかを確認できます。

于 2013-05-03T17:51:16.477 に答える