algorithm - 简化 T(n) 运行时

Question

给定以下功能

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？

Answer 1

让S(n) = T(n) + 1/2，然后S(n) = S(n-1) + S(n-2) + S(n-3)。

那么T(n)应该是c ₁ x ₁ ⁿ + c ₂ x ₂ ⁿ + c ₃ x ₃ ⁿ - 1/2，其中x _i是方程x ³ - x ² - x - 1 = 0和c _i的根是具体的系数。

T(n)的精确解有点复杂。实际上x ₁ = 1.84, x ₂ ,x ₃ = -0.42 ± 0.61i（是的，它们不是实数）。

但是，如果T(n)可以简化为T(n) = 3T(n-1) + 1，则T(n)必须类似于c ₁ x ⁿ + c ₀。因此，您无法进一步简化它。

Answer 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's 运行您的原始函数

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)s

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;
}