1 事后统计法

很多人疑惑，只需要把代码跑一遍，通过统计、监控就能得到算法执行的时间和空间大小。这种方式是正确的，但有以下两大局限性：

1. 测试结果非常依赖测试环境
2. 测试结果受数据规模的影响很大

2 时间复杂度分析

我们需要一个不用具体的测试数据来测试，就可以粗略的估计算法的执行效率的方法。

1. 只关注循环次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

2.1 几种常见时间复杂度

image.png
【注意】：对于上图的复杂度量级，粗略可分为：多项式量级和非多项式量级，非多项式量级只有两个：指数阶和阶乘阶。

2.2 最好、最坏情况时间复杂度

1. 最好情况时间复杂度就是，最理想的情况下，执行这段代码的时间复杂度
2. 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度

2.3 平均情况时间复杂度

以下例为分析：

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

要查找的变量x在数组中的位置，有n+1种情况：在数组的0~n-1位置和不在数组中。把每种情况下，查找需要遍历的元素个数加起来，再除以n+1，就可以得到需要遍历元素个数的平均值。

image.png
平时我们做平均复杂度分析时，一定要考虑到每种情况的概率。因此上面的推导应该将每种情况发生的概率也考虑进去，那么评价时间复杂度的计算就变成了：
image.png
这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

2.4 均摊时间复杂度

以下例为分析：

 // 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)，最好为O(n)，平均为O(1)。
但是我们分析，每次通过o(n)次的插入操作后，后面紧跟着n-1次O(1)插入操作，因此可以将耗时多的那次操作均摊到n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。
均摊时间复杂度的应用场景：在对一个数据结构进行一组操作中，大部分情况时间复杂度很低，个别情况复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候就可以将这一组操作放在一块分析，看是否能将较高时间复杂度那次操作耗时均摊到其他时间复杂度较低的操作上。【总结】：而且，能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况的时间复杂度。

3 空间复杂度分析

空间复杂度分析比较简单，我们常见的空间复杂度就是 O(1)、O(n)、O(n^2 )

4 内容总结

image.png