前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏欢迎大家来到数据结构专栏这篇博客是数据结构专栏的第一篇博客数据结构是和算法深度绑定的很多大学这门课叫做《数据结构与算法》在学习数据结构时也会随着学习一些高效的算法这篇博客会详细解析算法评判最基础的两个标准时间复杂度和空间复杂度这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1时间复杂度简介如果想衡量一段代码的效率如何那统计这个代码执行完成需要花费多少毫秒肯定是不合适的因为计算机的配置是有差异的时间复杂度就是用来“消除计算机的硬件配置差异”衡量一段代码执行效率的标准写一些复杂的代码时经常涉及到“重复性操作”时间复杂度就是以重复性操作作为基准单位衡量重复性操作的执行次数就可以作为判断代码执行效率的指标下面这段代码有for循环和while循环count就是一个“重复性操作”就是一个基准单位voidfunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;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){intcount0;for(inti0;i2*N;i){for(intj0;j2*N;j){count;}}for(intk0;k2*N;k){count;}intM10;while((M--)0){count;}System.out.println(count);}如果执行M N次M和N都是未知变量如下那么这段代码的时间复杂度就是OM Nvoidfunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}System.out.println(count);}代码执行的次数是固定的常数跟N没关系如下count固定执行100次可能初学铁汁会认为这里的时间复杂度就是O(100)其实不然只要是执行次数确定的也就是执行次数是常数时间复杂度都是O(1)因为随着N的增加执行次数是不会增长的voidfunc4(intN){intcount0;for(intk0;k100;k){count;}System.out.println(count);}2冒泡排序的时间复杂度接着分析下冒泡排序函数的时间复杂度代码如下voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){Swap(array,i-1,i);sortedfalse;}}if(sortedtrue){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){intbegin0;intendarray.length-1;while(beginend){intmid(endbegin)/2;if(array[mid]value)beginmid1;elseif(array[mid]value)endmid-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){returnN2?N:factorial(N-1)*N;}再比如计算斐波那契数下面这样写是一个非常低效的写法传入的数据稍微大一点计算机就要运行一段时间才能出结果intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}这个代码就是每次递归调用都再扩展成两个递归新扩展出的递归每个再扩展成两个递归执行次数是2的N次方时间复杂度就是O(N ^ 2)这个是非常非常高的已经远远高于O(N ^ 2)了甚至是O(N ^ 3)了计算第50个斐波那契数要执行的次数如下图已经是多少亿亿次了5空间复杂度空间复杂度也是通过O来表示的主要描述的是问题规模N和消耗的空间资源的变化趋势空间复杂度考虑的是计算机上的内存空间一般现在买计算机内存空间就是16G32G这样内存空间是关机断电后就不会保存的,而不是硬盘空间例如512G1T2T这种关机后数据还能保存创建的变量都是在内存上创建的堆空间和栈空间都是在内存上的注空间复杂度看的是临时占用的空间随着问题规模变化的增长趋势是不考虑问题本身的存储的例如下面这段代码参数传入了长度为N的数组那数组占用的存储空间是不计入时间复杂度中的看的是for循环中的比较逻辑占用的内存空间这里随着数组规模的增大就还是那几个变量并不会占用的内存空间更多因此下面代码的空间复杂度就是O(1)voidbubbleSort(int[]array){for(intendarray.length;end0;end--){booleansortedtrue;for(inti1;iend;i){if(array[i-1]array[i]){swap(array,i-1,i);sortedfalse;}}if(sortedtrue){break;}}}下面代码是计算斐波那契数效率较高的写法内存空间主要的消耗就是创建了一个数组随着问题规模变大消耗的内存空间就会增加数组的长度为N 1时间复杂度就是O(N)int[]fibonacci(intn){long[]fibArraynewlong[n1];fibArray[0]0;fibArray[1]1;for(inti2;in;i){fibArray[i]fibArray[i-1]fibArray[i-2];}returnfibArray;}下面这个递归计算数字阶乘的代码每次递归都会创建一个栈帧递归的深度是N也就有N份栈帧空间复杂度也就是O(N)longfactorial(intN){returnN2?N:factorial(N-1)*N;}计算斐波那契数的低效写法如下可能有的铁汁会认为空间复杂度是O(2 ^ N)其实并不是这样递归时空间是可以复用的因此一般只关心最深的递归的递归深度intfibonacci(intN){returnN2?N:fibonacci(N-1)fibonacci(N-2);}如下图这里最深的递归就是最左边f97线递归深度是N因此低效写法的空间复杂度也是O(N)结语时间复杂度和空间复杂度在数据结构的学习中会被经常提到在算法题目中更多提到的还是时间复杂度空间复杂度一般关注不多因为现在计算机的内存空间比较大不需要在写代码时去刻意节省内存这关系着代码的执行效率在蓝桥杯中如果代码时间复杂度过高就会出现部分用例超时的情况没办法得到全部的分数以上就是今天的所有内容啦完结撒花