《数据结构与算法之美》读后感——03（下）

一、分析例子一

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

以上是一个在一个无序的序列中寻找一个元素的算法，算法执行次数最多或者说核心部分是for循环里的代码，要计算时间复杂度就需要计算核心代码被执行的次数。核心算法的执行次数是随机的只和x是否在序列中和x在序列中的位置有关，x的位置越靠前，代码被执行的次数越少，反之越多。所以不能直接用上一节课的方法来计算算法的执行次数。在这种情况下算法的执行次数等于平均执行次数：

（每一种情况指的是待查找元素在序列中的位置）

平均执行次数 = 所有的情况的可能执行次数之和 / 所有的情况之和

设数据的规模是n

单种情况的可能执行次数 = 单种情况的执行次数 x 这种情况的出现概率

在队列中和不再队列中的概率分别为1/2，每种情况的概率为1/n

这种情况的出现概率 = 1/2n

所有的情况的可能执行次数之和 = 单种情况的可能执行次数之和

推导过程：

平均执行次数  = （3n+1）/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(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)

四、均摊时间复杂度

核心代码的执行次数有一定的规律的变化，如多次O(1)后是个别O(n)，可以把O(n)均摊到O(1)代码上，认为时间复杂度是O(1)

五、总结

如果核心代码的执行次数不仅和规模还和数据源的结构有关，如顺序，那么适合用平均时间复杂度分析，结果一般是最坏情况的时间复杂度。

如果核心代码的执行次数的呈现一个循环的规律，如多次O(1)后是个别O(n)然后循环，那么适用均摊时间复杂度，结果一般是最好的情况，如O(1)

图片来自极客时间 王争 《数据结构与算法之美》