如何解决以下复发？

Question

我不熟悉主定理,递归树和替换方法之外的递归求解技术.我猜测解决大O绑定的以下重现不会使用以下方法之一:

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

Answer 1

我们可以进行替换U(n) = T(n) + 1/2，然后得到重现

U(n) = T(n) + 1/2
     = T(n-1) + 2T(n-2) + 1 + 1/2
     = T(n-1) + 1/2 + 2(T(n-2) + 1/2)
     = U(n-1) + 2U(n-2),

这是一个小魔法，但是，正如 templatetypedef 提到的，可以使用 annihilator 方法来创建魔法。现在我们只需要解决线性齐次递归即可。特征多项式x^2 - x - 2因子为(x+1)(x-2)，因此解为U(n) = a(-1)^n + b2^n其中a和b为任意常数。等价地，T(n) = a(-1)^n + b2^n - 1/2，Theta(2^n)特殊情况除外。