复发关系

Question

如何计算最大复杂度的非常大的n(比如10 ^ 14)的tribonacci数.Tribonacci号码被定义为F(n)=F(n-1)+F(n-2)+F(n-3)与F0=1, F1=2, F2=4.

或复发定义为 F(n)=aF(n-1)+bF(n-2)+cF(n-3)用F0=1, F1=2, F2=4.

我想计算log(n)中的第n个项,就像第n个Fibonacci数一样.

如何生成基本矩阵以使用矩阵求幂来计算第n项？

以前我试图使用DP实现它,但因为我们不能采用这么大的数组它不能正常工作.类似地,递归在这里不起作用,因为堆栈溢出的数量非常大,为10 ^ 14.

Answer 1

tribonacci数的最佳渐近复杂度将使用矩阵求幂方法,如Fibonacci数的方法.具体来说,正确写入,这是O(log n)整数运算,而不是O(n)(如动态编程方法)或O(3 ⁿ)(如天真的解决方案).

感兴趣的矩阵是

    [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 ⁿ {F ₂,F ₁,F ₀ },也见这里.)

Answer 2

动态编程解决方案不需要10 ^ 14个元素阵列.它只需要3个.

请注意,每个步骤仅使用前3个元素,因此F(1000),您真的不需要F(5).

您可以简单地覆盖不再需要的元素,并将它们视为新数字.

%为此,运营商是您的朋友.