前言❤️❤️
hello hello💕，这里是洋不写bug~😄，欢迎大家点赞👍👍，关注😍😍，收藏🌹🌹
欢迎大家来到数据结构专栏🌹🌹🌹，这篇博客是数据结构专栏的第一篇博客，数据结构是和算法深度绑定的，很多大学这门课叫做《数据结构与算法》，在学习数据结构时，也会随着学习一些高效的算法
这篇博客会详细解析算法评判最基础的两个标准，时间复杂度和空间复杂度🐵
这个专栏的数据结构是代码都是用Java来写的，JavaSE专栏现在已经全部更新完成，铁汁们复习基础知识时非常推荐使用，可以试一下💪💪💪
🎇个人主页：洋不写bug的博客
🎇所属专栏：数据结构专栏
🎇复习Java基础知识：Java学习之旅，从入门到进阶
🎇铁汁们对于数据结构基础的各种核心知识（不太常用的也有😆），都可以在上面的数据结构专栏学习，专栏正在持续更新中🐵🐵，有问题可以写在评论区或者私信我哦~
1，时间复杂度简介
如果想衡量一段代码的效率如何，那统计这个代码执行完成需要花费多少毫秒肯定是不合适的，因为计算机的配置是有差异的
时间复杂度，就是用来“消除计算机的硬件配置差异”，衡量一段代码执行效率的标准
写一些复杂的代码时，经常涉及到“重复性操作”，时间复杂度就是以重复性操作作为基准单位，衡量重复性操作的执行次数，就可以作为判断代码执行效率的指标
下面这段代码，有for循环和while循环，count++就是一个“重复性操作”，就是一个基准单位
voidfunc1(intN){intcount=0;for(inti=0;i<N;i++){for(intj=0;j<N;j++){count++;}}for(intk=0;k<2*N;k++){count++;}intM=10;while((M--)>0){count++;}System.out.println(count);}count++的执行次数是N ^ 2 + 2N + 10，那这段代码的时间复杂度怎么算呢
当N = 100时，这时候2N + 10相比于N的平方就很小了，在计算时间复杂度时，就会把低次项给直接忽略掉
因此，这段代码的时间复杂度就是O(N^2)，时间复杂度并不关心精确的执行次数，只需要粗略知道随着N的增加，执行次数的增长趋势即可
如下所示，count++的执行次数改为4N^2 + 2N + 10，代码的时间复杂度还是O(N ^2)，计算时间复杂度时，最高项的系数是不考虑的，因为时间复杂度只需要粗略知道随着N的增加，执行次数的增长趋势即可
voidfunc1(intN){intcount=0;for(inti=0;i<2*N;i++){for(intj=0;j<2*N;j++){count++;}}for(intk=0;k<2*N;k++){count++;}intM=10;while((M--)>0){count++;}System.out.println(count);}如果执行M + N次，M和N都是未知变量，如下
那么这段代码的时间复杂度就是O（M + N）
voidfunc3(intN,intM){intcount=0;for(intk=0;k<M;k++){count++;}for(intk=0;k<N;k++){count++;}System.out.println(count);}代码执行的次数是固定的常数，跟N没关系，如下，count++固定执行100次，可能初学铁汁会认为这里的时间复杂度就是O(100)，其实不然
只要是执行次数确定的（也就是执行次数是常数），时间复杂度都是O(1)
因为随着N的增加，执行次数是不会增长的🐵
voidfunc4(intN){intcount=0;for(intk=0;k<100;k++){count++;}System.out.println(count);}2，冒泡排序的时间复杂度
接着分析下冒泡排序函数的时间复杂度，代码如下：
voidbubbleSort(int[]array){for(intend=array.length;end>0;end--){booleansorted=true;for(inti=1;i<end;i++){if(array[i-1]>array[i]){Swap(array,i-1,i);sorted=false;}}if(sorted==true){break;}}}时间复杂度就是看内层循环的次数，稍微观察下，就会发现内层循环的次数是一个等差数列，拿数组的长度当N来看，第一次循环N - 1次，第二次循环N - 2次
以此类推，内层循环总的执行次数就是N - 1 + N - 2 + N - 3 +… + 1
这个根据高中学过的等差数列的和的计算公式，总次数就是0.5N * (N - 1)
那时间复杂度就是O(N ^ 2)
但是，如果数组比较有序的话，那可能中途就通过break跳出循环了，前面计算的是最坏情况下的时间复杂度
如果最好情况下，那就是数组本来就有序，内层循环执行一遍就跳出了，那时间复杂度就是O(N)
这个冒泡排序函数，最坏情况下的时间复杂度是O(N ^ 2)，最好情况下的时间复杂度是O(N)，其实平均时间复杂度也是O(N ^ 2)，这里的平均也就是数组随机打乱来排序，计算出来的（有兴趣的铁汁可以搜下是怎么计算的）
我们是不需要关注考虑平均时间内复杂度是如何计算的，在绝大多数情况下，平均时间复杂度是和最坏时间复杂度是一样的，让计算时间复杂度的时候，直接按照最坏结果计算即可
就好比之前高考填志愿，是考前填的，需要估分，那肯定是要以最近模考最差的一次为参考，会比较稳，以最好的一次做参考肯定是不合适的
3，二分查找的时间复杂度
接着分析下二分查找的时间复杂度，代码如下：
intbinarySearch(int[]array,intvalue){intbegin=0;intend=array.length-1;while(begin<=end){intmid=(end+begin)/2;if(array[mid]<value)begin=mid+1;elseif(array[mid]>value)end=mid-1;elsereturnmid;}return-1;}二分查找每次while循环中的if执行一次，区间都会缩小一半，也就是每次都能排除一半的元素
计算时间复杂度直接按照最坏情况算，也就是要查找的元素不在数组中，推出2的比较次数次方等于总元素个数
比较次数也就是log2 N，因此，时间复杂度就是O(log2 N)
在计算机中，涉及对数的时间复杂度，大部分情况下都是以2为底的，当以2为底的时候，可以直接省略2不写，写成O(logN)
如果某个算法的时间复杂度是这种对数类型的，就可以认为是一个非常高效的算法
以ln为例（底数是2.7），数据规模是100万时，最多也只需要比较14次，如下图
而且随着数据规模的大幅增长，执行次数的增长是很少的
就算把数据规模从100万增加到为1亿，会发现执行次数也只是增加了几次而已，如下图
4，递归下的时间复杂度
有的代码，不一定把循环明面上写出来，而是通过递归的形式
就比如下面这个计算数字阶乘的代码，就是递归调用，这个也算是一种隐形的循环，时间复杂度就是O(N)
longfactorial(intN){returnN<2?N:factorial(N-1)*N;}再比如计算斐波那契数，下面这样写是一个非常低效的写法，传入的数据稍微大一点，计算机就要运行一段时间才能出结果
intfibonacci(intN){returnN<2?N:fibonacci(N-1)+fibonacci(N-2);}这个代码就是每次递归调用都再扩展成两个递归，新扩展出的递归每个再扩展成两个递归
执行次数是2的N次方，时间复杂度就是O(N ^ 2)，这个是非常非常高的，已经远远高于O(N ^ 2)了，甚至是O(N ^ 3)了
计算第50个斐波那契数，要执行的次数如下图，已经是多少亿亿次了😅
5，空间复杂度
空间复杂度也是通过O来表示的，主要描述的是问题规模N和消耗的空间资源的变化趋势
空间复杂度考虑的是计算机上的内存空间（一般现在买计算机内存空间就是16G，32G这样，内存空间是关机（断电）后就不会保存的）,而不是硬盘空间（例如512G，1T，2T这种，关机后数据还能保存）
创建的变量都是在内存上创建的（堆空间和栈空间都是在内存上的）
注：空间复杂度看的是临时占用的空间随着问题规模变化的增长趋势，是不考虑问题本身的存储的
例如下面这段代码，参数传入了长度为N的数组，那数组占用的存储空间，是不计入时间复杂度中的
看的是for循环中的比较逻辑占用的内存空间，这里随着数组规模的增大，就还是那几个变量，并不会占用的内存空间更多，因此下面代码的空间复杂度就是O(1)
voidbubbleSort(int[]array){for(intend=array.length;end>0;end--){booleansorted=true;for(inti=1;i<end;i++){if(array[i-1]>array[i]){swap(array,i-1,i);sorted=false;}}if(sorted==true){break;}}}下面代码是计算斐波那契数效率较高的写法，内存空间主要的消耗就是创建了一个数组，随着问题规模变大，消耗的内存空间就会增加
数组的长度为N + 1，时间复杂度就是O(N)
int[]fibonacci(intn){long[]fibArray=newlong[n+1];fibArray[0]=0;fibArray[1]=1;for(inti=2;i<=n;i++){fibArray[i]=fibArray[i-1]+fibArray[i-2];}returnfibArray;}下面这个递归计算数字阶乘的代码，每次递归都会创建一个栈帧，递归的深度是N，也就有N份栈帧，空间复杂度也就是O(N)
longfactorial(intN){returnN<2?N:factorial(N-1)*N;}计算斐波那契数的低效写法如下，可能有的铁汁会认为空间复杂度是O(2 ^ N)，其实并不是这样
递归时，空间是可以复用的，因此一般只关心最深的递归的递归深度
intfibonacci(intN){returnN<2?N:fibonacci(N-1)+fibonacci(N-2);}如下图，这里最深的递归就是最左边f97线，递归深度是N
因此，低效写法的空间复杂度也是O(N)
结语
时间复杂度和空间复杂度在数据结构的学习中，会被经常提到
在算法题目中，更多提到的还是时间复杂度（空间复杂度一般关注不多，因为现在计算机的内存空间比较大，不需要在写代码时去刻意节省内存），这关系着代码的执行效率，在蓝桥杯中如果代码时间复杂度过高，就会出现部分用例超时的情况，没办法得到全部的分数
以上就是今天的所有内容啦～完结撒花～🥳🎉🎉
