数据结构之时间复杂度&&空间复杂度的计算

数据结构：计算机如何存储数据的问题。DS关心的是如何高效的进行数据的读写。

算法：在特定的数据集上（不关心怎么进行具体数据的读写），如何利用数据完成特定的功能。算法本质上就是一系列运算的先后集合。

那么，如何评价一个算法的好坏？

从两种维度进行：时间效率与空间效率

时间复杂度：主要衡量一个算法的运行速度（不是实际计算机的运行速度，是理论值，在所有计算机上通用的描述） 

空间复杂度：主要衡量一个算法正常执行所需要的额外空间大小，不是当前数据集本身占用的空间

所谓额外空间：为了解决这个问题，新开辟的内存大小

1. 时间复杂度

不是具体的时间，在计算机领域，其实是一个数学函数。

因为不同的计算机硬件不同，相同的算法在不同的CPU，内存这些硬件上具体的执行时间都会有差异，而且差异还挺大！

那么，利用数学函数，描述一个算法的基本操作的执行次数，就是所谓的时间复杂度。

 在函数中，基本的执行语句可以不统计，基本语句和变量N毫无关系，时间复杂度看重的是执行次数和传入的变量之间的关系。

使用大O渐进表示法（数学函数，表示渐进函数）来描述一个算法的时间效率。

1.1 推导大O阶的方法：

（1）用常数1来代替函数中的所有加法常数（只要是常量，常数，都会1，无论常量有多大，用1代替）

因为常数和传入数值N变量毫无关系，此算法是一个稳定的时间效率算法，和变量无关！

（2）只保留函数的最高阶项，所有的低阶省略不计

（3）若最高阶项存在且项数不为1，统一将其最高阶的项数看做1

先看最高阶在哪，低阶全部省略；若没有变量参与，统一都是常数1。

例如：F(N)=N^2+2N+10                  时间复杂度：F(N)=O(N^2)

1.2 时间复杂度评价标准

一个算法的时间复杂度存在最好、最坏、平均时间复杂度。

• 最好：任意输入的数据，最小的执行次数（算法的下界）
• 最坏：任意输入的数据，最大的执行次数（算法的上界）
• 平均：任意输入的数据，平均的执行次数

eg：在长度为N的数组中，搜索一个数据x

最坏：若x刚好在数组的末尾或者不存在该数据，则需将整个数组进行遍历，执行N次才有结果

最好：若x刚好在数组首端，执行一次就能得到结果

平均：1+2+3+......+N=(1+N)*N/2(N个数据的总共查找次数)

           单个数据（(1+N)*N/2）/N =N/2       时间复杂度：O(N)

衡量一个算法的时间复杂度取上界，即考虑算法的最坏情况，使用大O阶时间复杂度来描述最坏情况就是整个算法的时间复杂度。

1.3 相关例题

1. 大O阶看的是变量的最高阶，若存在多个输入变量，都需要保留各个变量的最高阶。

此时N和M都是变量，无法得知N和M谁大谁小，推导大O阶时，N和M都保留其最高阶。

时间复杂度：O（N+M）

2. N和循环次数没有关系，循环次始终为100。O(1) 和变量N无关

时间复杂度：O(1)

 3.  冒泡排序

循环次数为N^2，内外层都执行N次。时间复杂度：O(N^2)

 4. 二分查找

该循环每次不是从0--N，而是每次从区间的中间位置将区间一分为二，mid=N/2；

n/2+n/4+n/8+.....+n/16+....，要求这个执行次数，以2为底N的对数 

时间复杂度：O(logn)

 public static int binSearch(int[] arr,int value){
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int mid=(right+left)/2;
            if(value
                right=mid-1;
            }else if(value>arr[mid])
            {
                left=mid+1;
            }else{
                return mid;
            }
        }
        //抛出运行时异常，代表未找到元素（不能返回-1，因为-1也有可能为元素本身）
        throw new NoSuchElementException("没有找到该元素！");
    }

（1）原则：忽略底数（换底公式：无论底数为多少，都可以换成以10为底的）

O(logn)==>忽略底数，即：对数级别的时间复杂度

如果一个算法能够做到对数级别的时间复杂度，则是非常优秀的！

（2）如何分析一个算法是对数级别的时间复杂度？

若算法是不断的将一个变量除以一个常数：N/2，或者N/3，一直除到为1或者0，则这个算法一定是对数级别的算法O(logn)，也叫折纸算法。

（3）分析O(N)、O(logN)、O(N^2)随着N的不断变化，三个不同函数的变化趋势。

 二分查找在一亿的有序集合中，最坏只需要29次就能查到特定元素。

5. 关于递归算法的执行时间分析

public static int fibo(int N){
        return N<=2? N:fibo(N-2)+fibo(N-1);
    }

执行次数：将fibo函数展开，执行次数就是下图中的方框个数，也就是说，求执行次数就是求结点的总个数。 

2+4+6+8+....+..... 求二叉树的节点个数：2^N+1==> 时间复杂度：O(2^N)

 public static int factor(int N){
        //1.base case
        if(N<=2){
            return N;
        }
        return N*factor(N-1);
    }

 执行次数：上述代码展开类比为：for(int i=1;i时间复杂度为O(N)

总结：看一个递归算法的时间复杂度，就看递归展开，函数的执行次数即可！

2. 空间复杂度 

 算法执行过程中，额外开辟的空间大小。

时间复杂度描述的是算法的执行次数；

空间复杂度描述的是一个算法额外开辟的临时变量个数，也是使用大O渐进表示法。

eg：冒泡排序的空间复杂度O(1)，额外开辟了一个临时变量temp。

2.1 分析空间复杂度

1. 斐波那契函数的空间复杂度

 public static int[] fibo(int N){
        int[] ret=new int[N+1];
        ret[0]=1;
        ret[1]=1;
        for (int i = 2; i<=N ; i++) {
            ret[i]=ret[i-1]+ret[i-2];
        }
        return ret;
    }

 由于函数中出现了new int[N+1];也就是说额外开辟了一个新数组，因此空间复杂度为O(N)。

2. 递归函数的空间复杂度

对于递归函数来说，每执行一次函数，就会在系统栈上产生新的栈帧，这就属于临时空间。

 public static int factor(int N){
        return N<=2?N:N*factor(N-1);
    }

也就是说观察其展开的次数。

空间复杂度：O(N)

总结：

非递归：空间复杂度就是看函数内部new了什么

递归：看函数的展开次数，每次调用一次函数，都会额外在栈上开辟栈帧空间。

一般空间复杂度最常见的为O(1)或O(N)

在题目中，出现空间复杂度要求为O(1)，代表此时不能开辟新的数组且不能使用递归。