复杂度分析(下)笔记:浅析最好、最坏、平均、均摊时间复杂度
最好时间复杂度和最坏时间复杂度在 渐近符号学习 中已经了解到了。
一、平均时间复杂度
// 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;
}
查找 x 在 数组中的位置,有 n + 1 中情况:在数组的 0~ n-1 位置 和 不在数组中。把每种情况下,查找需要遍历的元素个数累加起来,除以 n-1 就可以得到需要遍历的元素个数的平均值(查找总数/可能情况 = 每种情况的查找次数):
求时间复杂度,忽略低阶项和常量因子后:平均时间复杂度为:○(n)
image
这个结论虽然是正确的,但是计算过程实际上出了一些问题,我们没有将事件发生的概率计算进去。
什么概率呢?是变量 x 在数组中出现的概率和 出现位置的概率。出现在数组中和不出现在数组中的概率都为 ½ ,而出现在 0~n-1 这 n 个位置的概率为 1/n
。所以根据概率乘法法则,x 出现在数组中任意位置的概率为 1/(2n)
。
哎呦难受啊马飞,平均时间复杂度的计算过程又变了:
这个值就是概率论中的 加权平均值
,也叫作 期望值
。所以平均时间复杂度的全称应该叫做 加权平均时间复杂度
或者 期望时间复杂度
。
但是可但是,根据近似原则,常量因子和低阶项还有什么系数之类的都去掉后,这段代码的加权平均时间复杂度仍然是 ○(n)。
image二、均摊时间复杂度
均摊时间复杂度对应的分析方法为 摊还分析(平摊分析)
。均摊的应用场景比平均的应用场景更特殊,也就是说出现概率不高。
//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;
}
求上述代码的时间复杂度:
成员变量 count 小于 n 时,每次执行 insert()
方法,都在向数组中添加数据,此时所用时间为常量时间,则为:○(1)。(最好)
当成员变量 count 等于 n 时,执行循环语句,把数组中的数据累加到变量 sum 中,循环结束后将 sum 赋值给 数组下标为 0 的元素,将 count 重置为 1。此时所用时间为循环的遍历时间(取与n有关的时间,其他常量时间被忽略),则为:○(n)。(最坏)
每次插入数据时,若 count 小于 n ,则复杂度为:○(1)(出现 n 次)。若 count 等于 n,则复杂度为:○(n)。这 n + 1 种情况出现的概率是相同的,根据 加权平均的计算方法
:
问题:那么 insert() 与 find() 有什么不同之处呢?
不同之处在于 find() 只有在极端情况下(数组中无 x )复杂度才会为 ○(n),而 insert() 复杂度 ○(n) 出现的情况是有规律的:
执行 n 次插入操作后,会执行 1 次遍历操作
这种特殊的情况( 一个 ○(n)之后,紧接着就是 n - 1
个 ○(1)),可以使用一种更加简单的分析方法:摊还分析法。对应的时间复杂度称为 均摊时间复杂度
。
将执行循环的 ○(n) 均摊到每次执行插入的时间 ○(1),均摊下来,这一组连续的操作的均摊时间复杂度就为 ○(1)。
解释一下:
比如说,五个小朋友每个人吃1个苹果,然后一个大朋友自己吃五个苹果。均摊一下就是五个小朋友每个人吃两个。可以把对苹果的消耗理解为时间的消耗。所以一组满足特殊情况的操作的时间复杂度与n无关,是一个常量时间。
网友评论