斐波那契序列生成算法的优化 [英] Optimization of Fibonacci sequence generating algorithm

问题描述

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

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 .

这篇关于斐波那契序列生成算法的优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！