首先看一到leetcode题目:斐波那契数列。

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fibonacci-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一 : 本题非常明显可以通过递归来解决，代码如下

1
2
3
4

public int fib(int n){
		if(n <= 1) return n;
  	return fib(n-1) + fib(n-2)
}

但是这种方式在代码提交后，测试用例43超时，而题目给出的要求是[0,100]之内的数字,很明显算法需要优化。算法时间复杂度为O(2 ^ n), 空间复杂度为O(1).

接下来，我们尝试换一种算法解题

解法二 : 动态规划思想,利用dp数组存放每一位上斐波那契数列的值。

步骤： 1，定义初始化状态. dp[0] = 0; dp[1] = 1;

​ 2, 定义状态转移方程,非常容易得出结论. dp[n] = dp[n-1] + dp[n-2];

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  public int fib(int n) {
    	if(n <= 1) return n;
  		int[] dp = new int[n + 1];
	  	dp[0] = 0;
  		dp[1]= 1;
  		for(int i=2; i<= n; i++){
     	 		dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    	}
    	return dp[n];
 }

算法时间复杂度为O(n),空间复杂度为O(n).

解法三 ：优化空间复杂度，观察题目的值，第n位的值，只与第n-1位 和 第n-2位的值有关，所以是不是可以保存两个变量得出最终结果？

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  public int fib(int n) {
    	if(n <= 1) return n;
  		int first = 0;
  		int second = 1;
  		for(int i=2; i<= n; i++){
					int tmp = first;
					first = second;
					second += tmp;
    	}
    	return second;
 }

如上，以两个变量记录前值，算法时间复杂度同为 O(n)，空间复杂度从O(n)降低到 O(1).

如何评判一个算法的好坏？

从上述三种算法，可见算法的好坏，执行效率上会有很大差距， 所以如何评判一个算法的好坏？

有以下评判标准，

正确性，可读性， 健壮性（对不合理输入的反应能力和处理能力）

时间复杂度：估算程序指令的执行次数（执行时间）。

#大O表示法

一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度

忽略常数，系数，低阶 ，一般有 O(1)常数阶, O(logN)对数阶,O(n)线性阶,O(n ^ 2)平芳接,O(n ^ 3)立方阶,O(2 ^ n)指数阶等.

空间复杂度：估算所需占用的存储空间。

算法的优化方向：

1，用尽量少的存储空间

2，用尽量少的执行步骤（执行时间）

3，根据情况 可以空间换时间 或者 时间换空间