复杂度分析二

四种稍微复杂情况下的时间复杂度

1. 之前已经分析了常见的时间复杂度的分析情况，如O(1)、O(longn)....,除此之外，还有更为复杂的最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized case time complexity)。

最好最坏情况复杂度

1. 如下：

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

2. 该段代码主要是在无序的数组array中查找x所在的位置，查到返回，查不到则返回-1，间复杂度应该为：O(n),n代表数组的长度
3. 但是这段代码有一个明显的问题就是，就算在中途找到了X的位置，还会继续进行遍历查找，所以代码优化应该如下

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

4. 那么问题就来了，代码优化过后，时间复杂度还会是O(n)吗？因为要查找x的位置可能存在数组的任意位置中，如果x在第一个位置，则剩下的n-1个数据都不需要进行查找，此时的时间复杂度为O(1)，而如果x不存在数组中，则时间复杂度为O(n)，所以不同情况下的时间复杂度是不一样的
5. 为了表示不同情况下的时间复杂度，需要引入三个概念： 最好情况时间复杂度、最坏情况时间复杂度，平均情况时间复杂度

6. 最好情况时间复杂度，就是在最理想情况下的时间复杂度，如代码片段二中，如果x在数组的第一个位置，这时候对应时间复杂度就是最好情况时间复杂度，而最坏情况时间复杂度就是x不在数组中，这种情况就对应最坏情况时间复杂度

   
   平均时间复杂度分析.jpg

平均情况时间复杂度

1. 最好和最坏情况时间复杂度，都是在极端的情况下，发生的概率并不大，而为了更好的表示时间复杂度，需要引入平均时间复杂度
2. 要查找x所在的位置，有n+1种情况，在位置0~n-1和不存在数组中，把存在每个位置中的需要查询的次数进行相加，再除以n+1,就可以得到遍历次数的平均值
3. 而时间复杂度分析中，可以省略常量、系数、低阶，所以时间复杂度为O(n)
4. 在3中分析的时间复杂度存在一个问题，就是x存在数组中和不在数组中，概率都是1/2，那存在数组中时，在0~n-1的概率也是一样的，为1/n，所以根据乘法规则，存在数组中的概率为1/2n，因此将概率考虑进去的话，世家复杂度为如下：
5. 这个值就是加权平均值，也叫期望值，(3n+1)/4,用大O表示后，时间复杂度也是O(n)

6. 其实在大部分情况下，并不需要区分最好、最坏、平均时间复杂度，只需要取其中一个就OK了，只有当在同一块代码中，不同的情况时间复杂度存在量级的差距，才会采用这三种时间复杂度进行分析

   
   考虑概率的平均时间复杂度.jpg

均摊时间复杂度

TODO 吧，还没太搞明白

写在最后

1. 我的灵魂离我如此遥远，而我的存在却如此的真实