数据结构与算法之美:复杂度分析基础(下)
avatar
rhinoc
August 24, 2019

最好、最坏时间复杂度

COPY
find(nums,target){
    for (var i = 0; i<nums.length;i++){
        if (nums[i]===target) return i;
    }
}

对于上述代码,最好时间复杂度为O(1)O(1),最坏时间复杂度为O(n)O(n)

平均时间复杂度

一共有n+1n+1种情况:不在数组中和在数组的n个位置中。将这n种情况需要遍历的元素个数累加起来,再除以n+1n+1,就可以得到需要遍历的元素个数平均值。 简化后得到平均时间复杂度为O(n)O(n)

但根据各种情况发生的概率不同,还需要对以上公式进行调整。假设在数组和不在数组的概率均为12\frac{1}{2},其中,在数组中各个位置的概率均等,那么有:

得到加权平均值,也就是期望值。所以平均时间复杂度的全称应该叫「加权平均时间复杂度」或者「期望时间复杂度」。用大O表示法表示仍然为O(n)O(n)

大多数情况下,并不需要区分最好、最坏、平均时间复杂度三种情况,只有同一块代码在不同情况下,时间复杂度有量级的差距,我们才会使用这三种复杂度表示法来区分。

均摊时间复杂度

均摊时间复杂度的应用场景相对以上三种复杂度要更加特殊且有限。

COPY
var arr = [];
var count = 0;

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

上述代码的作用是往数组中插入元素,用count记录数组的长度(也可以理解为下一个元素的下标),当数组填满时,将数组中所有元素求和,存入数组第一个位置(下表为零),长度更新为1。(相当于舍弃了后面的元素)

如何求这段代码的时间复杂度呢?当count!=arr.length时,需要做的只是插入元素,故在这种情况下的时间复杂度为O(1)O(1);而当count===arr.length时,需要遍历数组进行求和,复杂度为O(n)O(n),那么平均时间复杂度可以这样计算:

但是这个例子下的平均复杂度计算不需要这么复杂,我们可以发现:O(n)O(n)O(1)O(1)的出现具有时序关系,一个O(n)O(n)插入之后,紧跟着n-1个O(1)O(1)的插入操作。

针对这种特殊的场景,我们引入了「摊还分析法」,通过这种方法求得得时间复杂度称之为「均摊时间复杂度」。也就是说,把1次耗时多的O(n)O(n)均摊到n-1次O(1)O(1),那么算得的均摊时间复杂度就是O(1)O(1)

可以将均摊时间复杂度理解为一种特殊的平均时间复杂度。

课后思考

分析下面代码的时间复杂度:

COPY
// 全局变量,大小为 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;
}

这段代码的分析方法其实和均摊时间复杂度的insert()函数一样的,最好时间复杂度为O(1)O(1),最坏时间复杂度为O(n)O(n),平均/均摊时间复杂度为O(1)O(1)

<TOC/>