[数据结构与算法 03] 最好、最坏、平均、均摊 时间复杂度

由来

• /****
      在一个无序的数组（array）中
      查找变量 x 第一次出现的位置。如果没有找到，就返回 -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;
  }

分析出此函数的时间复杂度为 O(n)

• 在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，
• 因为有可能中途找到就可以提前结束循环了。

所以我们可以这样优化一下这段查找代码

• /****
      在一个无序的数组（array）中
      查找变量 x 第一次出现的位置。如果没有找到，就返回 -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;
              break; // 已经找到了，就不必继续找了
          }
      }
      return pos;
  }

那么问题来了，如此优化以后，时间复杂度还是 O(n) 吗？？？

• 可能第一次就找到了，只循环了一次，那时间复杂度就是 O(1)
• 可能最后一次才找到，循环了 n 次，时间复杂度就成了 O(n)

所以，不同的情况下，这段代码的时间复杂度是不一样的

因此，为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念

• 最好情况时间复杂度
• 最坏情况时间复杂度
• 平均情况时间复杂度

2

2

2

2

2

2

2

2

一、最好情况 时间复杂度（best case time complexity）

在最理想的情况下，执行这段代码的时间复杂度

"只循环一次就找到了"

二、最坏情况 时间复杂度（worst case time complexity）

在最糟糕的情况下，执行这段代码的时间复杂度

"循环了 n 次才找到"

三、平均情况 时间复杂度（average case time complexity）

最好情况时间复杂度 和 最坏情况时间复杂度 对应的都是极端情况下的代码复杂度，发生的概率其实并不大。

为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，后面我简称为平均时间复杂度

1

1

1

1

四、均摊 时间复杂度（amortized time complexity）

1

1

1

1

1