算法复杂度入门指南从零看懂时间与空间复杂度一. 时间复杂度1.1 时间复杂度是什么1.2 例11.3 时间复杂度的计算(大O渐进法)1.4 多段循环相加1.5 常数阶 O(1)1.6 嵌套循环与多项式1.7 复杂度的本质1.8 忽略低阶项1.9 复杂度两变量1.10 o(1)与o(n)2.0常用时间复杂度练习冒泡排序二分查找二. 空间复杂度2.1空间复杂度的定义2.2 空间复杂度的计算规则2.3 空间复杂度示例分析冒泡排序2.4与时间的区别2.5 斐波那数列2.6递归算阶乘三. 实战 例题复杂度分析3.13.2四.包装类与泛型4.1基本数据类型与相应包装类4.2装箱与拆箱4.3自动装箱与拆箱4.4例题4.5泛型4.6泛型的应用一. 时间复杂度1.1 时间复杂度是什么时间复杂度就是程序代码运行只所执行的基本操作次数,可以是一个方法执行,变量运算;无论是时间复杂度还是空间复杂度都是用大O渐进法求大概数;基本操作就是一个被执行重复多次,他可以是一个变量的打印,变量的运算,只要他重复执行多次都可以算作一个基本操作1.2 例1for(inti0;in;i){count;}来看这个简单的代码其基本操作是count。循环执行了 n 次因此基本操作执行次数为 n。根据大 O 表示法其时间复杂度为 O(n)。1.3 时间复杂度的计算(大O渐进法)①取最高次项数②去掉最高次项的系数③常数都置为1,不管是0或1还是100或者更大的常数都当做11.4 多段循环相加publicvoidfunc(){intcount0;for(inti0;in;i){count;}for(intk0;k2*n;i){count;}intM10;while((M--)0){count;}}来看这个代码基本操作是count。我们需要分别计算三个循环的执行次数第一个for循环执行 n 次。第二个for循环执行 2*n 次。while循环执行 10 次。总的基本操作次数为n 2n 10。根据大 O 渐进法取最高次项n。去掉系数n。忽略常数项。因此该函数的时间复杂度为 O(n)。1.5 常数阶 O(1)inti1intcount0;while((i--)0){count;}这里的基本操作count在循环中执行了 100 次。根据大 O 渐进表示法常数次执行的时间复杂度记为O(1)1.6 嵌套循环与多项式publicvoidfunc(){intcount0;for(inti0;in;i){for(intj0;jn;j){count;}}for(intk0;k2*n;i){count;}intM10;while((M--)0){count;}}来看这个代码基本操作是count。第一个嵌套for循环执行 n * n n² 次。第二个for循环执行 2n 次。while循环执行 10 次。总的基本操作次数为n² 2n 10。根据大 O 渐进法取最高次项 n²去掉系数忽略低阶项和常数。时间复杂度为 O(n²)。1.7 复杂度的本质时间复杂度的本质是关注增长趋势的,例如o(n^2)o(2n^2)这两个其实是一样的,趋势差不多的;1.8 忽略低阶项publicvoidfunc(){intcount0;for(inti0;i2*n;i){count;}for(intj0;j10;j){count;}}时间复杂度:o(n)1.9 复杂度两变量publicvoidfunc(intN,intM){intcount0;for(inti0;iM;i){count;}for(intk0;kN;k){count;}}这个就跟之前的不一样了,有两个变量M,N还是计算时间复杂度o(MN)1.10 o(1)与o(n)对于o(1)和o(100),我们是不能直接比较谁更快或者谁更高效o(1)可能是o(1000)o(n)可能是o(100);或者o(1)可能是o(100)o(n)可能是o(1000);2.0常用时间复杂度练习冒泡排序这个就属于有实际运用的场景publicstaticvoidmy_sort(int[]array){for(inti0;iarray.length;i){booleanflatrue;//标记找好了for(intj0;jarray.length-i-1;j){if(array[j]array[j1]){inttemparray[j];array[j]array[j1];array[j1]temp;}}}}这个就有点难度了,还是来看,他内循环每一轮执行次数是不一样的第一轮:n-1;第二轮:n-2;第三轮:n-3;第四轮:n-4;第n轮:0;总共相加:01…23n-1n*(0n-1)/2得时间复杂度为(n2)二分查找publicstaticintbinarySearch(int[]arr,inttarget){intleft0;intrightarr.length-1;while(leftright){intmidleft(right-left)/2;// 防止溢出if(arr[mid]target){returnmid;// 找到目标返回索引}elseif(arr[mid]target){leftmid1;// 目标在右半部分}else{rightmid-1;// 目标在左半部分}}return-1;// 未找到}数组长度为1,最多比较1次数组长度为3,比较2次数组长度为7,比较3次数组长度为15,比较4次数组长度为n,比较次数为M2M-1nlog(n)默认底数为2所以时间复杂度为o(log(n))二. 空间复杂度2.1空间复杂度的定义我们所指的空间复杂度其实就是指内存里定义的变量,看定义变量,个数和问题规模N的趋势关系;2.2 空间复杂度的计算规则大o渐进法,还是依照这个2.3 空间复杂度示例分析冒泡排序publicstaticvoidmy_sort(int[]array){for(inti0;iarray.length;i){booleanflatrue;//标记找好了for(intj0;jarray.length-i-1;j){if(array[j]array[j1]){inttemparray[j];array[j]array[j1];array[j1]temp;}}}}在这里有三个变量的额外创建:int i,boolean fla,int j 0有些人有疑问,这里的boolean fla 不是每次循环都会创建一次吗?其实不是,变量他创建一次后会销毁然后创建,销毁一直这样,所以他最后还是额外只开辟一次的空间;2.4与时间的区别时间是过去就是过去了,而空间是可以重复利用的,总的消耗空间还是那么多;2.5 斐波那数列publicclassFibonacci{// 存储已计算的结果privatestaticint[]memo;publicstaticintfib(intn){memonewint[n1];returnfibHelper(n);}privatestaticintfibHelper(intn){if(n0)return0;if(n1)return1;// 如果已计算过直接返回if(memo[n]!0)returnmemo[n];// 计算并存储memo[n]fibHelper(n-1)fibHelper(n-2);returnmemo[n];}}空间复杂度:o(n)2.6递归算阶乘longfunc(intn){retun n2?:func(n-1);}开辟了n个空间递归也是会消耗额外空间的,也就是方法的调用,有一个特殊的空间叫做栈;三. 实战 例题复杂度分析分析以下函数的时间复杂度3.1voidfun(intn){intil;while(in)ii*2;}3.2for(inti0;in;i)for(intj0;jn;j)a[i][j]i*j;四.包装类与泛型4.1基本数据类型与相应包装类Java为了更好的面向对象,引入了包装类,但无法完全摒弃基础类,例如基础类的一系列运算,有了装箱和拆箱;4.2装箱与拆箱装箱基础类转换为包装类拆箱包装类转换为基础类publicstaticvoidmain(String[]args){// 装箱----valueOf()inti10;IntegerintegerInteger.valueOf(i);// 拆箱-----intValue();intjinteger.intValue();System.out.println(jj);}}4.3自动装箱与拆箱publicstaticvoidmain(String[]args){intnum10;Integerinum;//自动装箱System.out.println(i);intji;//自动拆箱System.out.println(j);}4.4例题publicstaticvoidmain(String[]args){Integera127;Integerb127;Integerc128;Integerd128;System.out.println(ab);System.out.println(cd);}答案:true false解析:JVM有着缓存,对于一些小的常用的数据,会提前创建好对象,后面使用的话直接引用就行,int的范围:-128~127所以127刚好可以直接用,a,b引用指向同一个创建好的对象4.5泛型这个虽然知识有点多,但没多重要,过一下,了解即可“泛”是广泛的意思,泛型意思就是广泛的类型例如我们创建一个数组String[]字符串数组int[]整型数组char[]字符数组…他可以是这些类型,但我们不可能都创建一下,那样效率太低了4.6泛型的应用publicclasstest4T//T表示的是泛型,我们也不知道是那种类型{privateObject[]arrnewObject[4];publicTgetArr(intindex){return(T)arr[index];}publicvoidsetArr(intindex,Tbate){arr[index]bate;}publicstaticvoidmain(String[]args){test4Stringtest1newtest4();// 此时T这个泛型就是String类型// 注意泛型的传入必须是数据类型的包装类test1.setArr(0,abc);test4Integertest2newtest4();test2.setArr(1,10);test4Charactertest3newtest4();test3.setArr(2,g);test4Doubletest4newtest4();test4.setArr(3,3.14);System.out.print(test1.getArr(0) );// 输出: abcSystem.out.print(test2.getArr(1) );// 输出: 10System.out.print(test3.getArr(2) );// 输出: gSystem.out.print(test4.getArr(3));// 输出: 3.14}}