math - 求解递归：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)。

标签： mathtime-complexityrecurrencemaster-theorem

Answer 1

这些类型的重复很棘手，不幸的是，重复扩展方法会让你一事无成。观察递归树只会给你一个上限，这个上限通常并不严格。

我可以建议两种方法：

---

1.替代+标准定理

进行以下变量替换：

这是Akra-Bazzi 方法的正确形式，带有参数：

---

2. 斐波那契公式

斐波那契数列有一个明确的公式，可以通过猜测形式的解来推导出Fn = a^n。以此作为类比，用类似的表达式代替T(n)：

使常数项和指数项相等：

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

这与(1)一致。