【跟我学Java就对了！！！】时间、空间复杂度

这块理解怎么算就行了。

1.时间复杂度

（1）概念

讲到时间复杂度，可能很多人都会觉得是计时，其实不是的，因为时间不好控制。

所以时间复杂度是按照基本操作的执行次数来记录的。

举个例子：

N是指问题规模，下面的代码可以吧N看作数字。


最坏情况就是最多执行次数。

平均情况就是任意规模的期望次数。

最好情况是最少运行次数。

（2）练习

①斐波那契数列的时间复杂度？

什么是斐波那契数列呢？

也就是0 1 1 2 3 5……这样的数列，也就是第三项是前两项之和。

看出来了吗？

所以，我们先来写一个斐波那契函数

class Fib{
    int ret =0;
    public int sfib(int x){
        if(x==0){
            ret = 0;
        }else if(x<3){
            ret = 1;
        }else if(x>2){
            ret = sfib(x-1)+sfib(x-2);
        }
        return ret;
    }
}
public class dd {
    public static void main(String[] args) {
        int x = 6;
        Fib fib = new Fib();
        int ret = fib.sfib(x);
        System.out.println(ret);
    }
}

那我们来分析一下啊：

这看起来像不像硕果累累的大树？

我们再来分析：

以上的数是一个实际的样子，但我们来抽象化一下：

所以它的时间复杂度，也就是执行次数 是这些的和，具体方法参考等比数列求和。

还要注意，其实斐波那契不是完全按照上面的抽象图的，实际会少一些递归次数。

看我画的树就知道了。

2.空间复杂度

（1）概念

临时需要额外占用的空间大小。
就比如我们拿数组来存储斐波那契数列，就会导致额外空间的占用。为什么呢？因为我们知识想求第20（假设）个斐波那契额数列，但我们需要知道前19个斐波那契额数列，所以我们需要临时存储前十多个斐波那契额数列。

现在的存储空间代价比较低，硬盘稍微便宜一些了，所以我们一般会拿更多的空间来换取时间，时间就是金钱，哈哈。