斐波那契序列生成算法的优化

本文介绍了斐波那契序列生成算法的优化的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

众所周知，生成斐波那契数列的最简单算法如下:

As we all know, the simplest algorithm to generate Fibonacci sequence is as follows:

if(n<=0) return 0; else if(n==1) return 1; f(n) = f(n-1) + f(n-2);

但是该算法具有重复性.例如，如果您计算f(5)，它将计算f(4)和f(3).当您计算f(4)时，它将再次计算f(3)和f(2).有人可以给我一个更省时的递归算法吗?

But this algorithm has some repetitive calculation. For example, if you calculate f(5), it will calculate f(4) and f(3). When you calculate f(4), it will again calculate both f(3) and f(2). Could someone give me a more time-efficient recursive algorithm?

推荐答案

在此处查找在Erlang中的实现使用公式.它显示出很好的线性结果，因为在 O(M(n)log n)部分中， M(n)对于大数是指数的.它以2s为单位计算一百万的fib，结果为208988位.诀窍在于，您可以使用(tail)递归公式(指的是 O(1)空间，当使用正确的编译器或重写时)来计算 O(log n)乘积的幂循环):

Look here for implementation in Erlang which uses formula . It shows nice linear resulting behavior because in O(M(n) log n) part M(n) is exponential for big numbers. It calculates fib of one million in 2s where result has 208988 digits. The trick is that you can compute exponentiation in O(log n) multiplications using (tail) recursive formula (tail means with O(1) space when used proper compiler or rewrite to cycle):

% compute X^N power(X, N) when is_integer(N), N >= 0 -> power(N, X, 1). power(0, _, Acc) -> Acc; power(N, X, Acc) -> if N rem 2 =:= 1 -> power(N - 1, X, Acc * X); true -> power(N div 2, X * X, Acc) end.

其中，您将 X 和 Acc 替换为矩阵. X 将以和标识为 I 的 Acc 等于.

where X and Acc you substitute with matrices. X will be initiated with and Acc with identity I equals to .