解决像复发斐波那契日志n次 [英] Solving a Fibonacci like recurrence in log n time

问题描述

查找第n项的斐波那契数列 F（N）= F（N-1）+ F（N-2）可以在O（n）的时间所记忆化解决。

Finding the nth term in Fibonacci series f(n) = f(n-1) + f(n-2) can be solved in O(n) time by memoization.

一个更有效的方法是找到矩阵的n次方[1,1]，[1,0]采用分而治之，解决了斐波那契日志n次。

A more efficient way would be to find the nth power of matrix [ [1,1] , [1,0] ] using divide and conquer to solve the Fibonacci in log n time.

有没有类似的方法可以遵循 F（N）= F（N-1）+ F（NX）+ F（N-X + 1）[x是一些恒定〕。

Is there similar approach which can be followed for f(n) = f(n-1) + f(n-x) + f(n-x+1) [ x is some constant ].

只是要存储previous x的元素，这可以在O（n）时间解决。

Just be storing previous x elements, this can solved in O(n) time.

有没有更好的办法来解决这个递归。

Is there a better way to solve this recursion.

推荐答案

因为你已经怀疑，这会工作非常相似。使用的的n次方X * X 基质

As you are already suspecting, this will work very similar. Use the n-th power of the x * x matrix

|1 0 0 0  .... 1 1|
|1 
|  1
|    1
|      1
|        1
...................
...................
|          ... 1 0|

这是容易，如果你用向量乘以这个矩阵理解

This is easy to understand if you multiply this matrix with the vector

f(n-1), f(n-2), ... , f(n-x+1), f(n-x)

这导致

f(n), f(n-1), ... , f(n-x+1)

矩阵求幂可以在O完成（的log（n））的时间（当x被认为是常数）。

Matrix exponentiation can be done in O(log(n)) time (when x is considered to be constant).

有关Fibonacci递推，还有一个封闭的公式的解决方案，在这里看到的 HTTP：//en.wikipedia .ORG /维基/ Fibonacci_number ，寻找比奈的或棣美弗公式。

For the Fibonacci recurrence, there is also a closed formula solution, see here http://en.wikipedia.org/wiki/Fibonacci_number, look for Binet's or Moivre's formula.

这篇关于解决像复发斐波那契日志n次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！