首页 » 算法 » 最好/最坏/平均/均摊时间复杂度

有时候算法的复杂度跟数据的排列由很大关系,这种复杂度不能简单的用一个复杂度来分析,而是由最好,最坏,平均复杂度来分析

1.如下面的,如果x在第0个位置,就是O(1),如果在第n-1个位置,就是O(n),这里就带表了最好和最坏


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

2.最好最坏的都是极端的,大概率不会发生,那么就引入了平均(情况)时间复杂度,那么x的位置,由n+1种情况,即在0~n-1的位置,还有不在数组种

  • 我们把每种情况的时间复杂度相加,除以可能出现的情况个数,就是平均时间复杂度---即1+2+3+4+...+ n 除以n+1,平均情况时间复杂度就是:n*(n+3)/2(n+1) 分子分母,逐步忽略常量,就是O(n)

3.加权平均时间复杂度,第二步中有点问题,就是没有考虑各种情况的概率,如果x出现在某个位置的概率非常大,那么上面的计算是把所有复杂度的情况都认为是1/(n+1)。

  • 实际上我们可以考虑,x在数组中的概率是1/2,x在每个位置的概率是1/n,那么x在某个位置的概率退化为1/2n,不在数组中的概率为1/2
  • 所以加权平均值是11/2n + 21/2n +...+ n1/2n + n1/2 = (3n+1)/4
  • 第二步的算法,是理想化了,每个情况的权重都看成了1/(n+1)

4.均摊时间复杂度---摊还分析,均摊时间复杂度就是一种特殊的平均时间复杂度,即只有1/n的情况复杂度是n(这里出现的概率很规律,比如数组插入n个数后必然发生扩容,不需要概率),那么均摊下来是O(1),而不需要通过平均计算

添加新评论