目录
??????????????导读概述
? ? ?互联网行业中数据结构和算法尤为重要,互联网软件特点：高并发、高性能、高扩展、高可用、海量数据,对编程的追求，了解数据结构和算法能让我们的代码精益求精。
? ? ?那如何评价算法的好坏呢，有2个重要的指标:时间复杂度和空间复杂度，时间维度是指算法运行结束消耗的时间，空间维度则是执行算法所需占用的内存空间。
本文将从以下几个方面分享给大家：
?1.什么是时间复杂度
?2.时间复杂度计算规则
?3.时间复杂度案例分析
?4.什么是空间复杂度
?5.空间复杂度计算规则
?6.空间复杂度案例分析
时间复杂度
-
算法的时间复杂度，也就是算法的时间量度,运行完算法需要的时间。
-
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系 。
如何计算一个算法的时间复杂度呢
通常采用大O表示法来表示
用 T(n) = O(f(n)) 表示
-
T(n)：表示算法执行总时间
-
n：数据规模
-
f(n)：表示每行代码执行总次数
-
O：代码的执行时间与f(n)表达式成正比
????????大 O 时间复杂度表示法,实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度（asymptotic time complexity）。
常见的时间复杂度大O表示法
1.O(1):常量级
//?大O表示法
int?a=1;
int?b=2;
int?count=a+b;这种是最简单的，也是最好理解的，就是常量级
不是只执行了一行代码，只要代码的执行不随着数据规模(n)的增加而增加，就是常量级
在实际应用中，通常使用冗余字段存储来将O(n)变成O(1)。
2.线性阶：O(n)
//?大O表示法
??int?sum(int?n){
????????int?count?=?0?;//t?一个时间单位
????????for(int?i=0;i<n;i++){//t*n
????????????count=count+i;//t*n
????????}
????????return?count;
????}????????上面的例子中时间复杂度T(n)=O(2n+1),当n无限大时，低阶、常量、系统都可以忽略
即上例中的时间复杂度为T(n)=O(n)，也就是代码执行时间随着数据规模的增加而增长
3.线性阶O(m+n)
//?大O表示法
??int?sum(int?m,int?n){
????int?sum1?=?0?;
????int?sum2?=?0?;
????for(int?i=0;i<=m;i++){//?O(m)
????????sum1+=i;
????}
????for(int?j=1;j<=n;j++){?//O(n)
????????sum2+=j;?
????}
????return?sum1+sum2;
}m和n是代码的两个数据规模，而且不能确定谁更大，此时代码的复杂度为两段时间复杂度之和,即?T(n)=O(m+n)
记作：O(m+n)
4.O(m*n)
//?大O表示法
????int?sum(int?m,int?n){
????int?sum?=?0?;
????for(int?i=0;i<=m;i++){//?m
????????for(int?j=1;j<=n;j++){?//m*n
????????????sum=i+j;?//m*n
????????}
????}
??return?sum;
??}
}根据乘法法则代码的复杂度为两段时间复杂度之积，即
T(n)=O(m*n)
记作：O(m*n)
当m==n时,为O()
5.平方阶 O(n^2)
//?大O表示法
??int?sum(int?n){
????int?count?=?0?;//t?一个时间单位
????for(int?i=0;i<n;i++){//n
??????for(int?j=0;j<n;j++){//n*n?
????????count=count+i+j;
??????}?
????}
????return?count;
}上例为：T(n)=O(n^2)
也就是代码执行时间随着数据规模的增加而平方增长
依此类推，时间复杂度也成为渐进增长：
两次嵌套for时间复杂度：O(n^2)
三层嵌套for时间复杂度：O(n^3)
k层嵌套for时间复杂度:O(n^k)
6.O(n^2)
//?大O表示法
?int?count?=?0?;//t?一个时间单位
????for(int?i=0;i<n;i++){
????????//O(n)
????}
????for(int?i=0;i<n;i++){//n
????????for(int?j=0;j<n;j++){//n*n
????????????count=count+i+j;
????????}
????}时间复杂度：?T(n)=O()+O(n)
简写：T(n)=O()?
注：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积(乘法法则)
7.对数阶?O(logn)
//?大O表示法
int?i=1；
while(i<n)
{
??????i=i*2;
}O(logn)推导过程:
以上代码，while循环中每次将i乘以2，直到i大于n，结束此循环。
如循环n次后，i>n，循环结束，也就是2的i次方等于n即i=log2n，也就是说循环log2n次以后，代码就结束了。代码的时间复杂度为O(logn)。
????????找出while循环中的结束条件，判断时间复杂度。带有while循环的代码，大概率是对数时间复杂度为
T(n)=O(n*logn)即O(logn)
小结：
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) <O (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(nn)
空间复杂度
-
算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数
-
空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
例如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:
记作：T(n)=O(2n)，忽略系数。即为O(n)
常见的空间复杂度
空间复杂度比较常用的有：O(1)、O(n)、O(n2)
1.O(1)空间复杂度
//?大O表示法
int?i?=?1;
int?j?=?2;
int?count?=?i?+?j;以下i，j和count变量所分配的临时空间不随处理数据量的变化而变化，因此它空间复杂度为O(1)
2.O(n)空间复杂度
//?大O表示法
?void?method(int?n)?{
????int[]?array?=?new?int[n];//O(n)
????for?(int?i?=?1;?i?<=?array.length;?++i)?{
????????//业务代码
????}
??}上述代码中的第一行代码new了一个数组，数组中有n个数据，剩余代码中虽然有循环，但是没有再分配新的空间，因此，该代码段的空间复杂度主要体现在第一行，为O(n)。平方阶的空间复杂度与之类似，依此类推即可。
常见的空间复杂度就是O(1)、O(n)、O(n^2)，而O(logn)、O(nlogn)空间复杂度平时用的少些。
?后记?
??????本文对算法中的时间复杂度和空间复杂度进行了简单的分析和介绍,希望对大家有所帮助,如果感觉有所收获，可以动动小手指给点个赞，感谢阅读!
微信扫码关注公共账号，谢谢阅读！
