为什么要进行复杂度分析？
在我们对一段代码的质量进行分析的时候，我们可能会把这一段代码直接运行一遍，根据统计、监控进行代码质量的分析。那我们对代码进行时间、空间复杂度的分析又有什么意义呢？
- 首先我们进行代码测试的时候不能够说把市面上所有的机器型号都拿过来运行一遍，这就造成了运行结果可能存在偏差。Intel和Arm处理器不同，系统不同等均有可能对代码运行的时间等造成影响。
- 其次是很多时候我们运行代码是要对数据进行分析。就以排序算法为例，数据是有序和无序的差别很大，如果我们进行运行测试的时候使用的是有序这种比较特殊的数据，得到的结果就也是特殊的，不具有普遍性。
大O复杂度表示法
首先我们看一个简单地程序：
1 void cal(int n) {
2 int i = 0;
3 int j = 0;
4 int sum = 0;
5 for (i = 0; i < n; i++) {
6 for (j = 0; i < n; i++) {
7 sum += sum;
8 }
9 }
10 }
第二行至第四行总共需要执行三句代码，而从第五行至最后需要执行n*2n句代码。虽然每句代码执行的时间是不一样，但是和实际运行时庞大的代码量相比，每句代码执行的时间可以近似认为是相等的，记为unit_time。那么上述代码运行所需的时间为（2n^2 + 3）* unit_time，可以看出来，所有代码的运行时间T(n)和每行代码执行的次数相关。我们可以得到一个规律：所有代码的执行时间与代码的执行次数成正比。
这个规律总结成公式就是：
T（n）= O（f（n））
其中f（n）代码代码执行的次数，T（n）代表代码执行的时间，O代表的就是正比例关系。
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的趋势，所以也叫做渐进时间复杂度，也叫做时间复杂度。
时间复杂度分析
分析时间复杂度有三个比较实用的方法
- 只关注循环次数最多的一段代码
- 加法原则：总复杂度等于量级最大的那段代码的复杂度，公式为：
如果T1（n）= O（f（n)），T2（n）=O（g（n））。则
T（n） = T1（n）+ T（2）= O（max(f（n）+ g（n）)） - 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，公式为
T（n）= T1（n）* T2（n）= O（f（n）* g（n））
这三个方法比较简单，就不予解释了，多计算几个复杂度就能理解。
常见的时间复杂度实例
该图中的时间复杂度量级可以粗略分为多项式量级和非多项式量级，其中非多项式量级随着数据规模n的增大，运行所需时间会极具增大，是一种低效的算法，所以我们只考虑多项式量级的时间复杂度。
常量阶O（1）
void cal(int n) {
int i = 0;
int j = 0;
int sum = 0;
sum = i + j;
}
对数阶O（log(n)）
void cal(int n) {
int i = 1;
int sum = 0;
while(i < n){
i = 2 *i;
}
}
线性对数阶O（nlog（n））
void cal(int n) {
for (int j = 0; j < n; j++) {
int i = 1;
int sum = 0;
while(i < n){
i = 2 *i;
}
}
}
至于平方阶、立方阶、k次方阶则是多个循环嵌套而成，这里就不写代码了。
特殊情况O（m+n）、O（m*n）
void cal(int n, int m) {
for (int i = 0; i < n; i++) {
//do something
}
for (int j = 0; j < m; j++) {
//do something
}
}
因为m与n的量级不知道，因此不能够是用加法法则进行比较，但是乘法法则还是适用的。
空间复杂度
空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
1 void print(int n) {
2 int i = 0;
3 int[] a = new int[n];
4 for (i; i <n; ++i) {
5 a[i] = i * i;
6 }
7 for (i = n-1; i >= 0; --i) {
8 print out a[i]
9 }
10 }
如代码所示，只有第三行新建了一个数组，这个数组的占用空间是和n相关的，其他的语句虽然也声明了变量，但是是常量阶的，与n是没有关系的。所以上述代码的空间复杂度就是O（n）。
课后思考
项目之前都会进行性能测试，再做代码的时间复杂度，空间复杂度分析是不是多此一举呢？
性能测试是感性的，我们可以直接看出代码运行所需要的时间资源，而代码的时间、空间复杂度是理性的，我们在写完代码的时候能够根据复杂度对这段代码有一个大致的认识。根据数据量级的不同，可能复杂度较高的算法运行所需的时间反而比复杂度低的算法较短，这个时候就需要性能测试来提供一个准确的保障，二者是相辅相成的。
设想一下，加入我们不进行时间、空间复杂度的计算，那么当我们算法写完之后完全不知道性能如何，每次修改之后都需要重新性能测试才能直到结果，这是多么麻烦啊。而只进行计算，不进行测试的话，就会出现不同量级的数据导致结果与我们预料的是完全相反的情况出现。
