求解递归关系：T（n）= T（n-1）+ T（n / 2）+ n

对于CS类，这是非常奇怪的重复。这是因为从一个角度来看：T(n) = T(n-1) + T(n/2) + n大于T(n) = T(n-1) + nO（n ^ 2）。

但是从另一个角度来看，泛函方程有一个精确的解：T(n) = -2(n + 2)。通过将其代入等式，您可以轻松地看到这是确切的解决方案-2(n + 2) = -2(n + 1) + -(n + 2) + n。我不确定这是否是唯一的解决方案。

这是我如何得到它：T(n) = T(n-1) + T(n/2) + n。因为你计算的东西很大n，比n-1几乎等于n。因此，您可以将其重写为T(n) = T(n) + T(n/2) + nis T(n/2) + n = 0，等于T(n) = - 2n，因此它是线性的。这对我来说是直觉相反的（这里是减号），但是有了这种解决方案，我尝试T(n) = -2n + a并发现了a的值。