Skip to content

复杂度分析

时间复杂度

  • 最坏时间复杂度:代码在最理想case下执行的时间复杂度
  • 最好时间复杂度:代码在最case况下执行的时间复杂度
  • 平均时间复杂度:用代码在所有case下执行的次数的加权平均值表示
  • 均摊时间复杂度:在代码执行的所有复杂度case中绝大部分是低级别的复杂度,个别case是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度

均摊时间复杂度

一个例子。往一个数组的末尾insert一个数。如果数组满了,就先把原有的数据求和,放在第一个位置,然后再从第二个位置开始,依次插入。

// 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(1),只有当数组满了的时候,是O(n)。且高级情况和低级情况存在时序关系。只有当n次都是低级,才会出现依次高级。

均摊时间复杂度两个条件满足时使用:

  • 代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;
  • 低级别和高级别复杂度出现具有时序规律。

均摊结果一般都等于低级别复杂度。