解决复发：T（n）= T（n - 1）+ T（n - 2）+ 3

Question

T（1）= T（2）= 1，并且对于n> 2，T（n）= T（n-1）+ T（n-2）+ 3。

到目前为止我做了什么：

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

我不确定这是否正确，如果是，我该如何摆脱T（n-4）。

Answer 1

这些类型的重现是棘手的，重复的扩展方法将遗憾地让你无处可去。观察递归树只会给你一个上限，这通常不紧。

我可以建议两种方法：

---

1.替代+标准定理

进行以下变量替换：

这是Akra-Bazzi method的正确形式，参数：

---

2.斐波纳契公式

Fibonacci系列有一个明确的公式，可以通过猜测Fn = a^n形式的解来得出。使用它作为类比，用T(n)替换类似的表达式：

等同于常数和指数项：

取正根，因为负根的绝对值小于1，因此随着n的增加会衰减到零：

这与（1）一致。