+
+
Posts List
  1. 最好、最坏时间复杂度
  2. 平均时间复杂度
  3. 均摊时间复杂度
  4. 课后思考

数据结构与算法之美:复杂度分析基础(下)

最好、最坏时间复杂度

1
2
3
4
5
find(nums,target){
for (var i = 0; i<nums.length;i++){
if (nums[i]===target) return i;
}
}

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

平均时间复杂度

一共有$n+1$种情况:不在数组中和在数组的n个位置中。将这n种情况需要遍历的元素个数累加起来,再除以$n+1$,就可以得到需要遍历的元素个数平均值。

简化后得到平均时间复杂度为$O(n)$。

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

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

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

均摊时间复杂度

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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)$;而当count===arr.length时,需要遍历数组进行求和,复杂度为$O(n)$,那么平均时间复杂度可以这样计算:

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

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

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

课后思考

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 全局变量,大小为 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(n)$,平均/均摊时间复杂度为$O(1)$。

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_3/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay