基础为技术之本_重新认识斐波那契数列

斐波那契数列，是软件人的一位老朋友了，今天我们就来回顾一下教科书上的写法以及这种写法性能上的弊端？有没有更好的写法？

1.首先，教科书的问法是求斐波那契数列的第n项；写一个函数，输入n,求出第n项目。数列定义如下：

 

于是接下来就会引申出递归函数的用法，以及代码（c#）实例：

 1 /// <summary>
 2 /// 斐波那契数列低级写法
 3 /// </summary>
 4 /// <param name="targetnumber">输入的目标值</param>
 5 /// <returns></returns>
 6 public int fibonacci(int targetnumber)
 7 {
 8 //算法开始
 9 if (targetnumber <= 0)
10 return 0;
11 if (targetnumber == 1)
12 return 1;
13 return fibonacci(targetnumber - 1) + fibonacci(targetnumber - 2);
14 }

 

得出结果并没有任何问题。但是这种写法可靠吗？是我们想要的吗？

我们来分析一下为什么这种写法会有很严重的效率问题。

首先我们求解f(10)，就需要得到f(9)与f(8),想要求解f(9)，势必要求出f(8)与f(7)，大家看到了吗？这种重复求解的关系是很糟糕的，并且会随着节点数会随着n的增大而急剧增大。如如下依赖关系图所示:

 

 那我们有没有更好的写法呢？当然有，因为递归与循环本来就是一家人！如下代码（c#）实例：

/// <summary>
/// 斐波那契数列高级写法 避免重复计算
/// </summary>
/// <param name="targernumber">输入的目标值</param>
/// <returns></returns>
public int fibonaccipro(int targetnumber)
{
stopwatch sw = new stopwatch();
sw.start();
//算法开始
int[] arraybase = {0, 1};
if (targetnumber < 2)
return arraybase[targetnumber];

int fibnumberone = 1;
int fibnumbertwo = 0;
int fibcurrentnumber = 0;

for (int i = 2; i <= targetnumber; ++i)
{
fibcurrentnumber = fibnumberone + fibnumbertwo;
fibnumbertwo = fibnumberone;
fibnumberone = fibcurrentnumber;
}

sw.stop();
timespan ts = sw.elapsed;
console.writeline("para is {0},datatime costed for shuffle function is {1}ms", targetnumber, ts.totalmilliseconds);
return fibcurrentnumber;
}

 

写完了之后我们来看一下性能方面到底是不是节约了很多?

首先，当参数n为10的时候：

这里已经可以初步看到效率有了明显的提升！

当参数n为30的时候，

这里的性能已经有了天翻地覆的差别！

 

 

除此之外，第一种方式的递归还有可能引起严重的栈溢出，每一次调用函数都会在内存栈种分配空间，而每个进程的栈容量是有限的，若第一种解法n参数为5000，则运行时候会出错，但是第二种解法则能得到正确结果。