复发关系

Tribonacci数的 _最佳_渐近复杂度将使用矩阵求幂方法，如Fibonacci数的方法。具体来说，这是正确的写 *** 作，它是O（logn）整数运算，而不是O（n）（如动态编程方法）或O（3n）（如朴素的解决方案）。

感兴趣的矩阵是

    [1, 1, 1]M = [1, 0, 0]    [0, 1, 0]

第 n 个tribonacci数位于 _M
n的_左上角。必须通过平方计算矩阵幂，以实现log（n）复杂度。

（对于

F(n+3) = a F(n+2) + b F(n+1) + c F(n)

    [a, b, c]M = [1, 0, 0]    [0, 1, 0]

结果为{F n + 2，F n + 1，F n } = M n {F 2，F 1，F 0}。）