寻找关系T(n) = T(n-1) + T(n-2) + T(n-3)的时间复杂度，当n > 3时。

Question

与斐波那契数列有些相似

算法的运行时间由以下给出

T (n) =T (n-1)+T(n-2)+T(n-3) if n > 3

= n，否则这个算法的阶数是多少？

如果通过归纳法计算，则

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

假设T(n)是一个函数aⁿ
那么 aⁿ = a^n-1 + a^n-2 + a^n-3
=> a³ = a² + a + 1

上述方程的根是复数，根据我的计算结果为：

a = 1.839286755
a = 0.419643 - i ( 0.606291) 
a = 0.419643 + i ( 0.606291) 

现在，我应该如何进一步处理或者是否还有其他方法可以实现这个目标？

- vCillusion

---

请查看Tribonacci数列。 - amit

询问 WolframAlpha - Ani

@Ani，那真是太棒了。神保佑你！！ - vCillusion

Answer 1

如果我没记错的话，当你确定了特征方程的根后，T(n)可以是这些根的幂的线性组合。

T(n)=A1*root1^n+A2*root2^n+A3*root3^n

所以我猜在这里最大的复杂度将会是(maxroot)^n，其中maxroot是您的根的最大绝对值。所以对于您的情况，它大约是1.83^n。

- sega_sai

---

非常感谢，这解决了我的问题。非常抱歉回复晚了！ - vCillusion

Answer 2

它可以近似表示为3+9+27+......3^n，这是O(3^n)。

- mukesh

Answer 3

渐近分析是针对程序运行时间的，它告诉我们随着输入的增加，运行时间将如何增长。

对于递归关系（如您提到的那个），我们使用两步过程：

1. 使用递归树方法估计运行时间。
2. 使用代入法验证（确认）估计值。

您可以在任何算法文本中找到这些方法的解释（例如Cormen）。

- Jonh