数据结构与算法之美笔记——复杂度分析(下)

摘要：

时间复杂度还可分为四种，分别是「最好时间复杂度」、「最坏时间复杂度」、「平均时间复杂度」和「均摊时间复杂度」。

为什么会引入这几种时间复杂度，是由于一段代码会出现多种情况，而在这些不同的执行条件下代码的执行效率会出现变化，所以需要引入这四种时间复杂度，可以更加全面地表达一段代码的执行效率。

最好、最坏时间复杂度

我们先来分析下列代码的时间复杂度。

int findTarget(int[] intArray, int n, int target) {
  int index = -1;
  for(int i = 0; i < n; i++) {
    if(intArray[i] == target) {
      index = i;
    }
  }

  return index;
}

这段代码中 n 表示数组的长度，可以分析出时间复杂度是 ，但是这段代码在查找到相应的数据下标后就可以中断循环，所以还可以优化一下。

int findTarget(int[] intArray, int n, int target) {
  int index = -1;
  for(int i = 0; i < n; i++) {
    if(intArray[i] == target) {
      index = i;
      break;
    }
  }

  return index;
}

此时再来分析时间复杂度就会遇到特殊情况，因为第 6 行代码的 break 使代码有几率可以不遍历完整个数组就结束循环，每次的循环次数就可能出现变化，那这种情况下时间复杂度又需要如何分析？

这段代码的循环会有极端情况和一般情况，先来分析极端情况，当 target 对应的数值出现在数组第一个或者最后一个(包括在数组中找不到对应数值情况)，这两种情况的时间复杂度分别为 和 ，这两种情况分别对应了最好情况和最坏情况，所以对应的这两种情况下分析得到的时间复杂度就是最好时间复杂度和最坏时间复杂度。

平均时间复杂度

分析完极端情况我们需要分析一般情况，一般情况下，target 对应数组中的数值有 n 种可能(在数组的第 1 位至第 n 位之间的任意一位)或数组中没有与target 对应的数值，所以总共有 种可能，那每种可能下需要循环的次数分别为 次，一般情况下需要循环的次数也就是 ，可根据数据公式作出如下推导。

忽略低阶，常量和系数后时间复杂度为

其实这段分析有些问题，因为忽略了与 target 对应的值出现在数组中和不出现在数组中的概率。先假设这两种情况下的概率相同，都是二分之一，由于目标数据出现在数组中每个位置的几率都为 , 所以 target 对应数组中每个位置数值的几率为 ，所以一般情况下循环的总次数为 ，最后的 是 target 对应值不在数组内的循环次数。

时间复杂度为

均摊时间复杂度

从名字上看与平均时间复杂度比较相似，但两者有很大的不同，先分析以下代码。

int[] intArray = new int[n];
int count = 0;

void insert(int val) {
  if(count == intArray.length) {
    int sum = 0;
    for(int i = 0; i < intArray.length; i++) {
      sum += intArray[i];
    }
    intArray[0] = sum;
    count = 1;
  }

  intArray[count] = val;
  count++;
}

利用之前的方式分析一下这段代码的时间复杂度，当数组没有被填充满时有 n 种可能，加上填充满的情况总共是 种情况，当填充满数组时会循环执行 n 次代码，所以代码的平均时间复杂度为

其实分析这段代码可以发现，循环 n 次的情况是规律出现的，当数组被填充 n - 1 次后就会出现循环 n 次，而 n - 1 次的操作时间复杂度是 ，循环的时间复杂度为 )。这种特殊场景下的时间复杂度分析可以使用摊还分析法，也就是说每次 操作后都会出现 n - 1 次 的操作，可以把耗时多的操作分摊到 n - 1 次时间复杂度低的情况上，所以时间复杂度为

均摊能够运用的场景比较特殊，而且能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好时间复杂度。

课后题目

用以上讲的几种时间复杂度分析下面这段代码。

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10]; 
int len = 10;
int i = 0;
 
// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个 2 倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来 array 数组中的数据依次 copy 到 new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array 复制给 array，array 现在大小就是 2 倍 len 了
     array = new_array;
     len = 2 * len;
   }
   // 将 element 放到下标为 i 的位置，下标 i 加一
   array[i] = element;
   ++i;
}

分析一下这段代码，功能就是向数组的末尾插入元素，当数组满后就把数组扩容两倍，而扩容时需要将之前数组的数据搬移至新数组中，此时就需要循环 n 次。

分析完代码，那最好时间复杂度就是数组未满时的插入为 ，最坏时间复杂度就是数组已满时搬移数组的情况为 。

因为每次扩容后数组就有 len 个空置可插入元素，再加上数组填充满后的 1 种可能，总共有 len + 1 种可能，前 len 种可能执行代码一次，最后一种可能会循环执行代码 len 次，所以

平均时间复杂度就为 。

依照上面分析，前 len 次时间复杂度都是 ，每隔 len 次就会有一次时间复杂度为 ，将 分摊到 次上，均摊时间复杂度就为 。

---

文章中如有问题欢迎留言指正
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。