时间复杂度和空间复杂度

1、概述

算法就是解决一个问题的方法，同一个问题使用不同的算法得到相同的结果，但是所消耗的资源是不等的，这就意味着我们需要从众多的算法中选出最优的那个算法。这个时候我们就不得不考虑这个算法的效率，而如何去评判或者判断一个算法的好坏，一个算法的效率如何，那就需要用到这两个指标：时间复杂性(消耗的时间)和空间复杂性(消耗的内存)。

2、时间复杂度

定义：时间复杂度(Time complexity)，个算法语句总的执行次数是关于问题规模N的某个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表示

统计方式：我们知道了什么是时间复杂度，那么我们怎么去计算呢？当然也有两种方式：一种是事后统计，算法写好之后统计算法的运行时间，当然如果一个算法很劣质，那么我们可能就需要推倒重来；另外一种就是事前分析，即在算法编写之前我们先分析其执行的时间复杂度，从而判断算法优劣

复杂度的计算：算法的运行时长我们可以理解为所有简单语句和每个简单语句运行的时长。赋值、比较、移动、判断、打印、一次数据库的操作等等我们都可以理解成是一个简单语句，从而：时间复杂度 = 简单操作的次数 * 一个简单操作的时间。一般一个简单语句的运行时长跟我们的计算机的硬件性能有关，但是硬件性能却与我们的算法质量无关，所以我们把每次简单语句的执行时间相同都是单位1，那么我们的时间复杂度就只与我们简单操作的次数相关。

例：有这样一个需求，给出10个数字，6,8,3,2,16,7,9,13,4,17。得知其中两个数字之和得26，找出这两个数据分别是几？

public class Test {
		// 定义所有数字的数组
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定义两数之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一个for循环得到第一个加数
        for (int i = 0; i < arr.length; i++) {
        		// 第二个for循环得到第二个加数，注意为了避免6+8 8+6这种重复，所以我们第二个加数直接把之前用过的数字去掉，节省一定循环次数
            for (int j = 0; j < arr.length; j++) {
            		// 拿着两个加数相加看得到的是否等于最终结果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}

分析：我们最终要执行的就是里面的一个判断，在这个里面我们总共执行了多少次呢？外面循环是10次，里面一个循环每次也执行10次，如果按照最差结果，那么要执行10的2次方一百次。如果我们有100个数，那么就是100的2次方就是一万次，如果再往上增加恐怕这个数值的恐怖程度会超出我们的想想吧,如此来说这个算法的时间复杂度是与数组长度有关系的假设我们数组长度是N，那么我们的计算次数就是N的2次方，事件复杂度与执行次数成正比，那么时间复杂度记为：O(n^2)

降低时间复杂度： 我们感觉上面那种方式时间复杂度太高了，那么有什么办法降低呢，看下面这种方式

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定义一个map存放能够得到目标数值的两个加数，key是当前值为了能得到最终值所需要的另一个加数，value就是我们当前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判断这个当前数值是否是之前数所需要的数值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }

分析：经过这次改造，看我们还需要执行多少次呢？原来需要两个循环，现在我们需要一个循环，那么需要执行N次能得到最终的结果。那么我们的时间复杂度为：O(n)

如果我们的一个算法，从头到位顺序执行不存在循环等条件，每行语句都执行一次或者固定次数，那么我们的时间复杂度就是O(1),那么我们总结一下，什么是时间复杂度，就是我们算法执行需要的时间，而怎么计算这个需要考虑我们算法中各个影响因素，以最重要因素为主去算我们的最终复杂度

3、空间复杂度

定义：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))

一个算法运行时所占用的空间一般分两部分，一个是固定的，指代码部分，就是我们的代码的多少，定义常量的，简单变量的多少；另一部分就是在我们代码运行中所产生的临时变量所占用的空间，这部分空间是不确定的，而我们所说的空间复杂度说的就是这部分空间的的占用情况

例: 我们延用上面的两个案例来分析一下他们的空间复杂度

case1

public class Test {
		// 定义所有数字的数组
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定义两数之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一个for循环得到第一个加数
        for (int i = 0; i < arr.length; i++) {
        		// 第二个for循环得到第二个加数，注意为了避免6+8 8+6这种重复，所以我们第二个加数直接把之前用过的数字去掉，节省一定循环次数
            for (int j = 0; j < arr.length; j++) {
            		// 拿着两个加数相加看得到的是否等于最终结果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}

分析：在这个案例里面在运行时我们没有定义任何变量，所以无论我们的数组元素变成多少，我们所占用的内存空间是固定的，那么我们的空间复杂度就是O(1)

case2：

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定义一个map存放能够得到目标数值的两个加数，key是当前值为了能得到最终值所需要的另一个加数，value就是我们当前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判断这个当前数值是否是之前数所需要的数值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }

分析：在case2中看到我们定义了一个map来存储数组元素，当我们开始运行时，map创建出来，随着我们数组元素的增多，我们map中所需要的空间也会不断增多，这个时候我们的空间复杂度就变成了：O(n)，n就是我们数组的长度

4、空间与时间

我们经常听到的一句话，利用空间换时间，利用时间换空间，其实在这里我们已经能深刻的体会出来了。这句话听着有点鱼与熊掌不可兼得的味道，但是目前来说大部分情况就是这个样子，有失有得，你总要付出一点代价方能得到一些。但是在我们目前的环境中这种选择似乎没有之前那么艰难，最开始的时候受资盘等的限制，一个程序的运行只有几K或者几百K，这个时候究竟是选择时间还是空间就会成为一个纠结的问题，随着计算机的发展，现在的磁盘内存等已经能够得到大部分需求的满足，所以在大部分情况下在选择空间与时间的问题上，选择时间的会偏多一点

不断努力，共同成长

关注公众号不迷路