复杂度分析：如何分析、统计算法的执行效率和资源消耗

事后统计法：

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

一、时间复杂度：

1. 表示算法的执行时间与数据规模之间的增长关系；
2. 只关注循环执行次数最多的代码；
3. 加法法则：总时间复杂度等于量级最大的那段代码的复杂度；
4. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；

几种常见的时间复杂度：

1. O(1)：一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万的代码，其时间复杂度也是O(1)；
2. O(logn)、O(nlogn)：在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n));
3. O(m+n)、O(m*n)：在无法事先评估m和n谁的量极大时，原来的加法法则就不正确了，需要将加法法则改为：T1(m) + T2(n) = O(f(m) + f(n))，但是乘法法则继续有效：T1(m) * T2(n) = O(f(m) * f(n))；

二、空间复杂度

1. 表示算法的存储空间与数据规模之间的增长关系；
2. 常见的空间复杂度：O(1)、O(n)、O(logn)；

总结：越高阶复杂度的算法，执行效率越低。常见复杂度从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)；

// 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;
}

三、最好情况时间复杂度

如上端代码：最好情况时间复杂度为 O(1);

四、最坏情况时间复杂度

如上端代码：最坏情况时间复杂度为 O(n);

五、平均时间复杂度

1. 如上端代码：平均情况时间复杂度为：
   
2. 这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫“加权平均时间复杂度”或者“期望时间复杂度”

六、均摊时间复杂度

1. 均摊时间复杂度就是一种特殊的平均时间复杂度

// 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;
 }

这段代码实现了一个往数组中插入数据的的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。
所以平均时间复杂度为：

3. 每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1);