基础为技术之本_重新认识斐波那契数列
程序员文章站
2022-04-29 14:21:34
斐波那契数列,是软件人的一位老朋友了,今天我们就来回顾一下教科书上的写法以及这种写法性能上的弊端?有没有更好的写法? 1.首先,教科书的问法是求斐波那契数列的第N项;写一个函数,输入n,求出第N项目。数列定义如下: 于是接下来就会引申出递归函数的用法,以及代码(c#)实例: 得出结果并没有任何问题。 ......
斐波那契数列,是软件人的一位老朋友了,今天我们就来回顾一下教科书上的写法以及这种写法性能上的弊端?有没有更好的写法?
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,则运行时候会出错,但是第二种解法则能得到正确结果。
上一篇: GAC 解释&路径
下一篇: 萝卜干怎么做好吃这个方法一学就会