在log n时间内解决斐波那契式复发

在log n时间内解决斐波那契式复发

正如您已经怀疑的那样，这将非常相似。使用

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公式。