algorithm - 在 log n 时间内解决类似斐波那契的递归问题

Question

求斐波那契数列的第 n 项f(n) = f(n-1) + f(n-2) 可以通过内存在 O(n) 时间内解决。

更有效的方法是使用分而治之法在 log n 时间内求解矩阵 [ [1,1] , [1,0] ] 的 n 次方。

是否有类似的方法可以遵循f(n) = f(n-1) + f(n-x) + f(n-x+1) [ x 是某个常数]。

只存储前面的 x 个元素，这可以在 O(n) 时间内解决。

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

Answer 1

正如您已经怀疑的那样，这将非常相似。使用 x * x 矩阵的 n 次方

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

如果将这个矩阵乘以向量，这很容易理解

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 被认为是常量时)。

对于斐波那契递推，也有一个封闭公式的解法，看这里http://en.wikipedia.org/wiki/Fibonacci_number , 寻找 Binet 或 Moivre 的公式。