事后统计法：把代码跑一遍，通过监控，就得到算法的执行时间和占用的内存大小。
为什么还需要对算法本身进行时间和复杂度分析呢？
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
因此需要通过一个不用具体的测试数据来测试，就可以粗略的估计算法的执行效率的方法。就是时间和空间复杂度。
时间复杂度
大O时间复杂度表示法（简称时间复杂度）：T(n)= O( f(n) ) 解释：T(n)是代码执行时间, f(n)是每行代码执行的总次数 ，O代表代码的执行时间T(n)与f(n)成正比。
例子：假设一行代码执行一次需要1个unit_time。
public int twoSum(int[] nums) {
int n = nums.length;
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum = nums[i] + nums[j];
}
}
return sum;
}这个代码的需要的时间为：T(n)= （2n^2 + 2n + 3），当n接近无穷大时，我们只需要关心n^2了，所以这个代码的时间复杂度为O(n^2)。
小方法：
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
| 排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不一顶 | O(n) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
简单理解下：什么情况下是O(logn)
i=1;
while (i <= n) {
i = i * 2;
}空间复杂度分析
简介：空间复杂度全称为渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
需要看代码申请了多大的占用空间，比如：
public int twoSum(int[] nums) {
int n = nums.length;
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
sum = nums[i] + nums[j];
}
}
return sum;
}这个空间复杂度是O(1)
我们常见的空间复杂度就是O(1)、O(n)、O(n^2)。像这种O(n*log2n)平常用不到，掌握之前的足够。
时间复杂度分析进阶
最好、最坏情况时间复杂度
public int find(int[] nums,int x) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] == x){
return i;
}
}
return -1;
}这段代码在最好情况下时间复杂度为O(1) ，最坏情况下时间复杂度为O(n)
平均时间复杂度
大多数时间，使用一个复杂度就可以了。
平均时间复杂度分析法需要计算每一个可能出现的可能及加上一部分概率。
均摊时间复杂度
/**
* 代码实现了往数组中不断插入数据。当数组满了，就将所有元素之和赋值给首位。如此周而复始。
**/
// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;
// 会有程序不断调用 insert() 方法
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(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。
