这是我参与新手入门的第二篇文章。

前言

语言只是工具，而算法才是程序的灵魂。今天我们以斐波那契数列为例来看下算法里的复杂度计算。

一、斐波那契数列

1.定义：

首先我们要知道什么是斐波那契数列：又称黄金分割数列，这个数列从第3项开始，每一项都等于前两项之和。

F[n]=F[n-1]+F[n-2] (n>=2,F[0]=0,F[1]=1)

2.实现方案

方法一 ：使用递归方案计算

 public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
 }
复制代码

方法二：

public static int fib2(int n) {
       if (n <= 1) return n;
       int first = 0;
       int second = 1;
       for (int i = 0; i < n - 1; i++) {
           int sum = first + second;
           first = second;
           second = sum;
       }
       return second;
}
复制代码

3.执行结果

我们使用System系统自带的获取时间戳的方法来记录方法耗时：

当n=10:

当n=45:

当n=49:

我们可以从执行结果中看出：
当n越大，fib1 的耗时就要比fib2越久。

4.分析

我们看到fib1 的代码行数要比fib2少很多，定义的变量也少，但是却耗时更多，那么到底如何评价一个算法的好坏呢？

• 正确性、可读性、健壮性。
• 时间复杂度（time complexity） 估算程序指令的执行次数（执行时间）
• 空间复杂度（space complexity）估算所需占用的存储空间

二、时间复杂度

1.定义

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

常用大O表示法。 (Big O)。他表示的数据规模N 对应的复杂度 O(n)。有多个数据规模的话就是 O(n,j)
。大O表示法是一种粗略的分析模型。 是一种估算。帮助我们短时间内了解一个算法的执行效率
特性是忽略常数、系数、低价。

2.复杂度估算

复杂度依次递增：

3.斐波那契数列方法估算

根据我们所说的大O表示法。我们可以估算一下，使用递归方案的fib1 的时间复杂度为O(2ⁿ)，而fib2的时间复杂度为O(n)。所以当n越大的时候fib2几乎不会耗费更多的时间。

三、空间复杂度

1.定义

空间复杂度（space complexity）估算所需占用的存储空间。
与时间复杂度一样，空间复杂度时估算一下占用空间的大小。

O(1) 一个对象空间

O(n) N个对象空间

四、算法优化方向

随着设备更新，我们更多的会采取空间换时间的方案来优化用户体验。也需要考虑业务需求等因素的影响。

• 尽量少的存储空间

• 尽量少的执行步骤

• 空间换时间，时间换空间

结尾

慢慢记录所学，一点点的积累，不断的更新补充，希望能够保持这样的一个习惯。望各位多多指教，共勉之。