递归 Tribonacci 序列时间复杂度

Question

你如何计算递归 tribonacci 函数的时间复杂度 F(n) = F(n-1) + F(n-2) + F(n-3) 与基本情况 F(0) = 0, F(1) = F(2) = 1？

Answer 1

用归纳法更容易证明O(1.84^(n-1))。
T(n) = 1 当 n <= 2 和 T(n) = T(n-1) + T(n-2) + T(n-3) 当 n > 2.

基本情况：
T(3) = 1 + 1 + 1 = 3
T(3) = 1.84^2 ≈ 3
T(3) = O(1.84^(n-1))

归纳案例：假设T(n-1) = 1.84^(n-2)。那么，
T(n) = T(n-1) + T(n-2) + T(n-3)
T(n) = 1.84^(n-2) + 1.84^(n-3) + 1.84^(n-4)
T(n) ≈ 1.84^(n-1)
T(n) = O(1.84^(n-1))

如果您希望它准确，请改用 tribonacci constant，但显示它相等很乏味。但是，如果您愿意，我可以编辑它以显示它。