在log n时间内解决斐波那契像复发一样

Question

在Fibonacci系列中找到第n项f(n)= f(n-1)+ f(n-2)可以通过记忆在O(n)时间内求解.

一种更有效的方法是使用除法和征服来找到矩阵[[1,1],[1,0]]的n次幂,以便在log n时间内求解Fibonacci.

是否有类似的方法可以遵循f(n)= f(n-1)+ f(nx)+ 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被认为是常数时).

对于Fibonacci重复,还有一个封闭的公式解决方案,请参见http://en.wikipedia.org/wiki/Fibonacci_number,查找Binet或Moivre的公式.