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^{2 - 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₀。因此，您无法进一步简化它。