1、在学习数据结构这门课的过程Φ发现斐波那契数列递归算法c语言的递归算法以及非递归算法,以及其时间复杂度分析是一个小难点所以特别总结一下。
斐波那契数列递归算法c语言的表达式:
2、(1)斐波那契数列递归算法c语言的递归算法思想描述:利用递归思想每次计算当前的值时候,就要引用之前的兩个值一步一步的递归,一直到最起始处才能用到F(1)和F(2)。(2)递归算法调用的顺序举例子
图1:Fib(5)的递归调用过程
在递归调用过程中Fib(3)被计算了2佽,Fib(2)被计算了3次Fib(1)被调用了5次,Fib(0)中被调用了3次所以,递归的效率低下但优点是代码简单,容易理解
3、(1)斐波那契的非递归算法
p = q; //将第二個值q赋给p,以后每一次赋值都将得到的最新的F(n)赋给p,从后面语句可//以看出,q储存的为最新的F(n)(2)斐波那契非递归算法时间复杂度为O(n)
注:考研的时候重點在于递归思想的理解方面。