algorithm - 重复关系

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 个斐波那契数一样。

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

以前我试图使用 DP 来实现它，但由于我们不能采用如此大的数组，所以它不能正常工作。同样，由于 10 ^ 14 的大量订单的堆栈溢出，递归在这里不起作用。

score 13 · Accepted Answer

tribonacci 数的最佳渐近复杂性将使用矩阵求幂方法，例如Fibonacci 数的方法。具体来说，正确编写，这是 O(log n) 整数运算，而不是 O(n)（如动态规划方法）或 O(3 ⁿ )（如天真的解决方案）。

感兴趣的矩阵是

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

并且第n个 tribonacci 数在M ⁿ的左上角。必须通过平方来计算矩阵求幂以实现 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 ₀ }，另见此处。）

score 7 · Accepted Answer

动态编程解决方案不需要 10^14 元素数组。它只需要 3。

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

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

%为此，运营商是您的朋友。

2 回答 2