复发关系 [英] Recurrence Relations

问题描述

如何以最大的复杂度计算非常大的n（例如10 ^ 14）的百龙数。 Tribonacci数字定义为 F（n）= F（n-1）+ F（n-2）+ F（n-3） F0 = 1，F1 = 2，F2 = 4 。

或循环定义为
F n = 1，F 1 = 2，F 2 = 4，...，f 0 = 1， code>。

我想像第n个斐波纳契数字一样计算log（n）中的第n个项。

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

以前，我正在尝试使用DP来实现它，但是我们不能采取这么大的数组，它的工作不正常。类似地，递归在这里没有工作，因为堆栈溢出非常大的10 ^ 14的顺序。

解决方案

>最佳对于Tribonacci数字的渐近复杂性将使用矩阵求幂方法，如斐波纳契数字。具体来说，这是O（log n）整数运算，而不是O（n）（如动态规划方法）或O（3 ⁿ ）（如初始解） p>

感兴趣的矩阵是

  [1，1，1] 
 M = [1，0，0] 
 [0，1，0] 
  

和第i个第三个Tribonacci号码位于 M ⁿ 的左上角。必须通过计算通过平方来实现log（n）复杂度来计算矩阵求幂。

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 n =子>，F ₁ ，F ₀ }，还看到这里。）

How to calculate tribonacci number for very large n ( say 10^14 ) in best complexity. Tribonacci numbers are defined as F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

Or recurrence defined as F(n)=aF(n-1)+bF(n-2)+cF(n-3) with F0=1, F1=2, F2=4.

I want to Calculate nth term in log(n) just like nth Fibonacci number.

How can I generate the Base Matrix for using matrix exponentiation to calulate the nth term?

Previously I was trying to implement it using DP but as we cannot take array of such large size its not working fine. Similarly Recursion didn't work here due to stack overflow for very large numbers of order of 10^14.

解决方案

The best asymptotic complexity for tribonacci numbers will be using a matrix exponentiation method like the one for Fibonacci numbers. Specifically, written correctly, this is O(log n) integer operations, rather than O(n) (like the dynamic programming method) or O(3ⁿ) (like the naive solution).

The matrix of interest is

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

and the nth tribonacci number is in the upper left corner of Mⁿ. The matrix exponentiation must be computed by squaring to achieve log(n) complexity.

(for F(n+3) = a F(n+2) + b F(n+1) + c F(n), the matrix is:

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

and the result is {F_n+2,F_n+1,F_n} = Mⁿ {F₂,F₁,F₀}, also see here.)

这篇关于复发关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！