递归Tribonacci序列时间复杂度

Question

如何用基例F(n) = F(n-1) + F(n-2) + F(n-3)计算递归tribonacci函数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常数代替，但它是乏味的显示它是相等的。但是，如果您愿意，我可以编辑它来显示它。