0. 序言
数据结构和算法解决的是“快"和"省"的问题，即"如何让代码运行得更快"以及"如何让代码更省内存空间"。而衡量代码运行时间的标准，我们称之为"时间复杂度";衡量代码占用空间的标准，我们称之为”空间复杂度"。
这篇文章通过简单的示例，带你入门复杂度分析，而更多的复杂度分析后续会写文章阐述。
1. 为何需要复杂度分析
你可能会对代码的复杂度分析有疑问，觉得代码的时间和空间复杂度通过代码的执行，并在此执行的过程中监控、统计就能获得，为何还要进行复杂度分析呢？不可否认，这也是一种计算代码时间和空间复杂度的方法，叫事后统计法，只是这种方法有局限性，因为这些局限性，会导致复杂度的统计不准确。
- 测试结果非常依赖测试环境
测试环境中硬件的不同会对测试结果有很大影响。比如说i9和i3处理器处理同一段代码，i9的执行速度快很多。 - 测试结果受数据的影响很大
拿排序来说：
① 同一个排序方法，数据有序度不一样的话，排序的执行时间就会有很大的差别。
② 小规模的数据排序，插入排序可能会比快速排序要快。
综上：我们需要一个不用具体的测试数据来测试，就可以粗略地计算代码的执行效率的方法，也就是这篇文章要讲解的时间和空间复杂度分析法。而时间和空间复杂度分析完毕后，我们总要阐述出来，而通常我们采用大O复杂度表示法来阐述时间和空间复杂度。
2. 大O复杂度表示法
int cal(int n) {
int sum = 0; // 1
int i = 1; // 2
for (; i <= n; ++i) { // 3
sum = sum + i; // 4
}
return sum; // 5
}
CPU在执行的过程中总是执行类似操作：读数据-运算-写数据。因为是粗略估计，所以我们可以忽略诸如CPU核数等差异条件。那么在这种粗略计算下，我们假设每行代码的执行时间相同，称之为unit_time，即单位时间。那以上代码的总执行时间是多少呢？
代码1和代码2以及代码5都需要一个单位时间unit_time,而代码3和代码4执行了n遍，都需要n个unit_time,这段代码执行总共需花费的时间是（3+2n）× unit_time，这里我们把代码的总执行时间称为T(n)。
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
通过上面的分析，我们可以得出这段代码总执行时间T(n) = (2n2+2n+3)*unit_time。
综上：所有代码的执行时间T(n)与每行代码的执行次数成正比。用公式来表示：
T(n) = O(n)
① n：表示数据规模的大小。
② O：表示代码的执行时间T(n)与数据规模的大小成正比。
所以上面的示例用大O复杂度表示法表示分别是T(n) = O(3+2n)和T(n) = O(22+2n+3).所以大O复杂度表示法并不具体表示真正的执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，简称时间复杂度。所以当n很大的时候，公式中的常量、系数并不左右增长趋势，所以可以忽略，我们只记录一个最大量级就可以了，所以上面的示例用大O复杂度表示法也可以表示为：T(n) = O(n)和T(n) = O(n2).
3. 简单的时间复杂度分析
这里讲解代码时间复杂度分析的三个方法：
- 只关注循环执行次数最多的一段代码：
int cal(int n) {
int sum = 0; // 1
int i = 1; // 2
for (; i <= n; ++i) { // 3
sum = sum + i; // 4
}
return sum; // 5
}
这里代码1和2和5都是常量级的执行时间，而代码3和4循环次数最多，我们只关注循环执行次数最多的一段代码，所以总的时间复杂度是O(n)。
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
sum1段代码的时间复杂度是常量级，尽管是循环，但只要有明确的次数，代码的时间复杂度是O(1)。sum2段代码因为循环了n次，所以时间复杂度是O(n),同理sum3段代码的时间复杂度是O(n2)。根据加法法则：这三段代码的时间复杂度，加起来就是O(1)+O(n)+O(n2)，而我们取最大量级，所以这段代码的时间复杂度是O(n2)
- 乘法法则: 嵌套代码复杂度是嵌套内外代码复杂度的乘积
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
这段代码有两层嵌套，所以这段代码的复杂度是O(n * n) = O(n2)
4. 空间复杂度分析
时间复杂度，也叫做渐进时间复杂度，同样，空间复杂度，也叫做渐进空间复杂度，表示算法的存储空间与数据规模之间增长关系。
常见的空间复杂度有O(1),O(n),O(n2)，而O(logn)和O(nlogn)这样的对数阶复杂度平时用不上。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
分析空间复杂度，就分析哪些代码占用内存。经过分析发现，以上代码中只有容量为n的数组和常量i占用空间，根据加法法则，这段代码的复杂度为O(n).
5. 后续
如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!
