斐波那契数列理解

斐波那契额数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……，这是由数学家列昂纳多·斐波那契由兔子引入的，又称为兔子数列。

斐波那契数列是我第一个入门算法，最开始经典解法是用递归的形式。

//n：想要得到第几个数是多少
public static void fibo(int n){
	if(n < 1){
		return 0;
	}
	if(n == 1 || n == 2){ //base case
		return 1;
	}
	return fibo(n-1) + fibo(n-2); //recursive case
}
           

分析：上面就是斐波那契经典实现要想写好一个recursion，首先我们要有一个base case也就是递归到最后触底反弹的那个条件，如果没有base case，则方法就会陷入无限递归当中，而递归的第二个精髓点在于要有recursive case 也就是递归的情形，总体思想是利用分治的思想如上题，我们要求前n个数的和，由斐波那契的数列我们不难发现 第三个数总是等于前两个数的和，于是我们不难推出 f(n) = f(n-1) + f(n-2)

fibo(5)              ....Ot(1)
			/      \
		fibo(4)  fibo(3)          ....Ot(2)
		/   \        /   \
	fibo(3) fibo(2)fibo(2)fibo(1) ....Ot(4)
	/   \                           :
fibo(2) fibo(1)                   ....Ot(2^n-1)
           

空间复杂度：O(n) 根据冯诺伊曼计算机工作原理可知fibo(5)会调用fibo(4)然后4在调用3 知道碰到base case 触底反弹 所以空间复杂度为fibo(5)开始的左子树的那条边 所以时间复杂度为O(n)

时间复杂度：O(2^n) 所有用Ot() 符号表示所使用时间的累加和1+2+4+…+2^n-1 = 2^n

经典版的斐波那契时间复杂度是指数级别所以我们需要优化一下 下面是时间复杂度O(n)的顺序遍历版：

/**
     * 顺序遍历版 时间复杂度O(n) 空间复杂度O(1)
     * @param n
     * @return
     */
    public static int fibo2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = 0;
        int a = 1;
        int b = 1;
        int temp = 0;
        for(int i = 3;i <=n ;i++) {
            temp = b;
            res = a + b;
            b = res;
            a = temp;
        }
        return res;
    }
           

分析：

时间复杂度因为遍历了从3-n所以时间复杂度是O(n)

空间复杂度O(1)

总结：

1.递归精髓在于分治将一个大问题分治的思想将大问题分成多个小问题 merge sort就是一个例子

2.递归算法要设计好base case 也就是他中止条件，还有就是递归情形也就是让他不断的缩小的过程让他继续递归下去