重要性
复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
测试结果非常依赖测试环境
测试结果受数据规模的影响很大
我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。
大 O 复杂度表示法
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2nunit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
这就是大 O 时间复杂度表示法，大 O 时间复杂度实际上并不具体代表代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫做 渐进时间复杂度，简称 时间复杂度。
分析时间复杂度
-
只关注循环执行次数最多的一点代码
我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
空间复杂度分析
时间复杂度的全称是 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
复杂度种类
-
最好情况时间复杂度
最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
-
最坏情况时间复杂度
最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。
平均情况时间复杂度
均摊时间复杂度
例子：
// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个 2 倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来 array 数组中的数据依次 copy 到 new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array 复制给 array，array 现在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 将 element 放到下标为 i 的位置，下标 i 加一
array[i] = element;
++i;
}
最好 ，最坏
，平均
，均摊
参考自极客时间
