4

次の関数が与えられます

int g(int y) {
  if (y <= 0) {
    return 1;
  } 
  else {
    return g(y-1) + g(y-2) + g(y-3);
  }
}

T(n)実行時間を見つける必要があります。今、私はあなたが書くことができることを知っています

T(n) = T(n-1) + T(n-2) + T(n-3) + 1

これをさらに単純化できるかどうかはわかりませんT(n) = 3T(n-1) + 1。

4

2 に答える 2

7

S （n）= T（n）+ 1/2とすると、S（n）= S（n-1）+ S（n-2）+ S（n-3）となります。

その場合、 T（n）はc 1 x 1 n + c 2 x 2 n + c 3 x 3 n -1/2である必要があります。ここで、xiは方程式x3 -x 2 - x --1 =0およびciの根です。特定の係数です。

T（n）の正確な解は少し複雑です。実際には、 x 1 = 1.84、x 2、x 3 = -0.42±0.61i（はい、実数ではありません）。

ただし、T（n）を簡略化してT（n）= 3T（n-1）+ 1のように形成できる場合、T（n）はc 1 x n +c0のようにする必要があります。したがって、これ以上単純化することはできません。

于 2012-10-14T06:42:59.403 に答える
2

あなたの機能はそうではありません

T(n) = T(n-1) + T(n-2) + T(n-3) + 1

です

if n > 2
    T(n) = T(n-1) + T(n-2) + T(n-3)
or 
    T(n) = 1, 3, 5 for n = 0, 1, 2 respectively.

確認するには、次の「y」を使用して元の関数を実行します

g(0) = 1
g(1) = 3
g(2) = 5

g(3) = 9 (i.e. = g(0) + g(1) + g(2) = 9, not g(1) + g(2) + g(3) + 1 = 10)

動的計画法を使用して、すでに計算されたT（n）の再計算を回避します

int g(int y)
{
    if(y <= 0)
        return 1;

    if(y ==  1)
        return 3;

    if(y == 2)
        return 5;

    int a1 = 1; int a2 = 3; int a3 = 5;
    int ret = 1;

    for(int i = 2; i < y; ++i)
    {
        ret = a1 + a2 + a3;
        a1 = a2;
        a2 = a3;
        a3 = ret;
    }

    return ret;
}
于 2012-10-14T07:03:00.550 に答える