如何判断程序的复杂程度：时间和空间复杂度

1、如何判断程序的复杂程度：时间和空间复杂度时间复杂度：使用大O表示法来表示程序的时间复杂度常见的7种时间复杂度(复杂度由低到高排序)0(1):常数时间复杂度O(log(n):对数时间复杂度O(n):线性时间复杂度0(nA2):平方时间复杂度0(nA3):立方时间复杂度0(n):指数时间复杂度，k表示常数0(n!):阶乘时间复杂度ps：这里我们并不考虑前边的系数；0(1)并不表示复杂度为1,也可以是2、3等常数；0(n)表示程序运行了n次或者2n、3n次；以此类推其他时间复杂度时间复杂度的判断，以一段代码的最高复杂度为准；如何判断一段代码的时间复杂度简而言之就是看内部某段代码的执行次数0(1):常

2、数复杂度intn=1;System.out.println(n);12intn=1;System.out.println(n);System.out.println(n+1)System.out.println(n+2)12340(n):线性时间复杂度for(intj=0;jn;j+)System.out.println(j);123for(inti=0;in;i+)System.out.println(i);for(intj=0;jn;j+)System.out.println(j);1234560(nA2):平方时间复杂度for(inti=0;in;i+)for(intj=0;jn;j+)

3、System.out.println(i+j);12345O(nA3):立方时间复杂度for(inti=0;in;i+)for(intj=0;jn;j+)for(intk=0;kn;k+)System.out.println(i+j);1234567O(log(n)：对数时间复杂度这里演示的是以2为底n的对数for(inti=0;in;i=i*2)System.out.println(i);1230(2切)：指数时间复杂度/*递归求斐波那契数列的第n项；可以通过画运行树的方式获得时间复杂度*/intfib(intn)if(n2)returnn;returnfib(n-1)+fib(n-2);1

4、234567O(n!):阶乘时间复杂度todo小练习1:求和计算1n的和O(n)inty=2;for(inti=0;in;i+)y+=i;1234O(1)使用了求和公式：sum=n(n+1)/2inty=2;for(inti=0;in;i+)y+=i;1234小练习2:求斐波那契数列O(2An):intfib(intn)if(n2)returnn;returnfib(n-1)+fib(n-2);1234O(n):该方法比递归要快得多intfib2(intn)if(n=1|n=2)return1;inta=1,b=1,result=0;for(inti=3;i=n;i+)result=a+b;a

5、=b;b=result;returnresult;123456789101112主定理主定理(英语：mastertheorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法常用算法中的应用算法递回关系式运算时间二分搜寻算法二叉树遍历最佳排序矩阵搜索(已排好序的二维矩阵)合并排序所有排序的最优算法都是O(nlog(n)空间复杂度如何判断一段代码的空间复杂度主要通过两部分进行判断：数组的长度如果代码中应用了数组，那么数组的长度，基本上就是空间复杂度；e：维数组的空间复杂度是O(n);二维数组的空间复杂度是O(n)递归的深度如果代码中有递归，那么递归的深度，就是代码的空间复杂度的最大值ps:如果代码中既有数组，又有递归，那么两者的最大值就是代码的空间复杂度leecode有个爬楼梯的复杂度分析情况；可以进行练习数组和链表的时间复杂度分析数组随机增加：O(n)随机查询：O(1)随机删除：O(n)链表随机增加：O(1)随机查询：O(n)随机删除：O(1)跳表跳跃表(skiplist)是一种随机化的数据，由WilliamPugh在论文Skiplists:aprobabilisticalternativetobalancedtrees中提出，跳跃表以有序的方式在层次化的链表中保存元素，效率