斐波那契据数算法优化

斐波那契数算法优化

      在很多算法都用到了递归算法，谈到递归就难免要提到斐波那契数的算法。

     最一般的算法如下(C#语法)：        

 private long Fibonacci(int n)
        {
            if (n == 1 || n == 2)
                return 1;
            else if (n > 2)
                return Fibonacci(n - 1) + Fibonacci(n - 2);
            else
                return 0;
        }

    运行测试下，发现当参数n=39时运行速度就变的很慢了,我计算了下，大概3－4秒,而当n=42时，已然要10来秒才能完成，当n=45时就没反应了，一两分钟都没有结果。

    其实仔细分析下可以Fibonacci方法在被调用后，向下调用就翻倍地调用了下一级的Fibonacci方法。

    计算了一下，假设斐波那契数数列的第N项的值是an(n)的话，那么调用上面的递归算法，Fibonacci方法会被调用 an(n) *2 +1 次，当n=39时an(39)=63245986,Fibonacci方法被调用了126491971次，效率之低可以见一斑。

   这里我做了下优化，算法如下：

private long Fibonacci(int n,out long m)
        {
            long t, r;
            if (n == 1)
            {
                m=0;
                return 1;
            }
            else if (n == 2)
            {
                m = 1;
                return 1;
            }
            else if (n > 2)
            {
                t = Fibonacci(n - 1, out m);
                r = t + m;
                m = t;
                return r;
            }
            else
            {
                m = 0;
                return 0;
            }
        }

此处的最大优化在于保存计算项之前的每一项的值，每一项的计算只调用Fibonacci方法一次，实际调用Fibonacci方法的次数只有n-1次，如果n=33，那么调用Fibonacci方法只有32次。

    看看方法的调用次数就可知算法的效率了。

1楼sueking1分钟前

an=1/√[（1+√5/2) n-(1-√5/2) n](n=1,2,3.....）（√5表示根号5）