如何解决以下递归问题？（涉及IT技术）

Question

除了主定理、递归树和代换法之外，我不熟悉其他的循环求解技巧。我猜测解决下面这个循环求解式的大O边界并没有使用那些方法:

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

- velen

---

T(n) 的基本情况是什么？ - Tim Biegeleisen

这是一个很好的使用湮灭法的地方……但我实际上不知道如何做。 :-) - templatetypedef

没有提供基本情况。我猜不需要实现大O边界？ - velen

提示：T(n) = 2^n。此外，请查看这个数学StackExchange问题。 - displayName

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所提到的，可以用消灭者法则来创造这种魔幻。现在我们只需要解决线性齐次递推关系。特征多项式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)，除了特殊情况外。

- David Eisenstat

Answer 2

这个递归被称为非齐次线性递推关系，可以通过将其转化为齐次递推关系来解决：

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

从2中减去1并更改基数，得到 T(n) = 2 T(n-1) + T(n-2) - 2 T(n-3)。相应的特征方程为：

x^3 - 2x^2 - x + 2 = 0

这意味着该递归具有解 x = {-1, 1, 2}。因此，该递归看起来像：

c1 * (-1)^n + c2 * 2^n + c3 * 1^n = c1 * 2^n + c2 (-1)^n + c3

这里的所有常数都可以通过已知的T(0)和T(1)来确定。根据您的复杂度分析，很明显这是指数级的，即O(2^n)。

- Salvador Dali