简化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 ₀.因此,您无法进一步简化它.