复杂度分析包括：
- 时间复杂度分析
- 空间复杂度分析
事后统计法
我们常用事后统计法来统计效率，这种方法也存在一些问题例如：
1，测试结果依赖测试环境
2，测试结果受数据规模的影响很大
大O复杂度表示法
代码执行时间随着数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。
T(n)=O(logn)
T(n)=O(n)
T(n)=O(n*logn)
T(n)=O(n^2)
一般有这几种复杂度
时间复杂度分析
在cpu的角度看，每行代码都在执行类似的操作：读数据-运算-写数据，每行简单看成一次操作
例如：
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;
}
}
}
上面代码可以看成执行了（2n^2 + 2n + 3）*unit_time
1，只关注循环执行次数最多的一段代码
我们在分析一段代码的时间复杂度的时候，也只是关注循环执行次数最多的那一次代码。其他的相对可以忽略不计
2，加法法则：总复杂度等于量级最大的那段代码的复杂度。
一段代码有几段循环，例如单次循环和嵌套循环，嵌套循环的复杂度是量级更大的。
3，乘法法则：嵌套代码的复杂度等于嵌套内外代码的复杂度的成绩
例如：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
两个方法嵌套，并且是循环嵌套就等于两个复杂度的积
复杂度的量级
- 多项式量级
常量阶O(1)
对数阶O(logn)
线性阶O(n)
线性对数阶O(nlogn)
平方阶O(n^2)
立方阶O(n^3)
K次方阶O(n^k) -
非多项式量级
指数阶O(2^n)
阶乘阶O(n!)
一般非多项式量级的称为NP(Non-Deterministic Polynomial)非确定多项式问题。当n越大，执行时间会急剧增大，这种算法的时间复杂度是非常低效的。
复杂度.jpeg
复杂度分析有几种情况
- 最好情况的时间复杂度
- 最坏情况的时间复杂度
- 平均情况的时间复杂度
- 均摊时间复杂度
前面三个都好理解，下面说说这个复杂度分析
/ array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
例如上面的例子，当没达到数组的长度的时候复杂度是是O(1),在达到length的时候复杂度O(n),想这样规律的多个低阶复杂度+一个高阶复杂度的情况，这个高阶复杂度可以分摊到前面n个低阶的复杂度上。他最终的复杂度是O(1)，像这种多个低阶可以把一个高阶的给分摊掉就是均摊复杂度。比如ArrayList的insert导致的扩容也是一个道理。
均摊复杂度也算是一种特殊的平均复杂度。
空间复杂度
时间复杂度的全称是渐进时间复杂度，标识算法的执行时间与数据之间的增长关系，类比空间就是渐进空间复杂度，标识算法的存储于存储空间规模之间的增长关系。
主要的空间复杂度O(1)、O(n)、O(n^2)，而O(logn)、O(nlogn)基本用不到。
