最好、最坏、平均、均摊时间复杂度
Varsion
  • 最好情况时间复杂度(best case time complexity)
  • 最坏情况时间复杂度(worst case time complexity)
  • 平均情况时间复杂度(average case time complexity)
  • 均摊时间复杂度(amortized time complexity)

最好、最坏情况时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
def find (Ar,x)
len = Ar.length
i = 0
pos = -1
for i in 0..len
if Ar.at[i] == x
pos = i
break
end
end
return pos
end

该段代码的功能是,在一个无序数组Ar中查找变量x出现的位置,如果没有找到就返回-1len表示该数组的长度,根据复杂度分析来看,该段代码的复杂度为O(len)

但是我们在数组中查找数据,并不需要每次都把该数组遍历一遍,因为可能中途找到该元素而提前结束循环。

因为要查找的元素可能在数组任意位置,如果数组第一个元素就是要查找的x,那就不需要再遍历之后的len-1个元素了,这时的复杂度是O(1)。但如果数组中不存在该元素,或者该元素在最后一个位置,那么此时的复杂度即为O(len)

所以,代码在不用情况下的不同时间复杂度,这里引入了三个概念:最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。

顾名思义,最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。在最理想的情况下,对应的时间复杂度就是最好情况时间复杂度。

同理,最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。就像刚举的那个例子,如果数组中没有要查找的变量 x,我们需要把整个数组都遍历一遍才行,所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。

平均情况时间复杂度

这里仍然使用刚刚的例子:

要查找的变量 x 在数组中的位置,有 len+1 种情况:在数组的 0~len-1 位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值:

(1+2+3+4+…+len+len)/len+1 = len(len+3)/2(len+1)

同样使用大O标记法,省略掉系数、低阶变量、常量简化之后,复杂度为O(n)

这个结论虽然是正确的,但是计算过程稍微有点儿问题。我们刚讲的这 n+1 种情况,应该考虑到概率问题。应该根据概率乘法法则来重新计算:

计算结果根据大O标记法简化之后,复杂度仍为O(n)

均摊时间复杂度

均摊时间复杂度,听起来跟平均时间复杂度有点儿像。对于初学者来说,这两个概念确实非常容易弄混。大部分情况下,并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Ar = Array.new(n)
count = 0

def insert(val)
if count == Ar.length
sum = 0
for i in 0...Ar.length
sum = sum + Ar.at(i)
end
Ar.clear
Ar[0] = sum
count = 1
end
Ar[count] = val
++count
end

这段代码实现了一个往数组中插入数据的功能。当数组满了之后,也就是代码中的 count == Ar.length 时,我们用 for 循环遍历数组求和,并清空数组,将求和之后的 sum 值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。

最理想的情况下,数组中有空闲空间,只需要将数据插入到数组下标为 count 的位置就可以了,所以最好情况时间复杂度为 O(1)。

最坏的情况下,数组中没有空闲空间了,需要先做一次数组的遍历求和,然后再将数据插入,所以最坏情况时间复杂度为 O(n)。那平均时间复杂度是多少呢?答案是 O(1)。我们还是可以通过前面讲的概率论的方法来分析。

假设数组的长度是 n,根据数据插入的位置的不同,我们可以分为 n 种情况,每种情况的时间复杂度是 O(1)。除此之外,还有一种“额外”的情况,就是在数组没有空闲空间时插入一个数据,这个时候的时间复杂度是 O(n)。而且,这 n+1 种情况发生的概率一样,都是 1/(n+1)。所以,根据加权平均的计算方法,求得的平均时间复杂度就是:

11/(1+n)+…+n1/(n+1) = O(1)

来对比一下这个 insert() 的例子和前面那个 find() 的例子,这两者有很大差别。

首先,find() 函数在极端情况下,复杂度才为 O(1)。但 insert() 在大部分情况下,时间复杂度都为 O(1)。只有个别情况下,复杂度才比较高,为 O(n)。这是 insert()第一个区别于 find() 的地方。

再来看第二个不同的地方。对于 insert() 函数来说,O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作,循环往复。

所以,针对这样一种特殊场景的复杂度分析,并不需要像之前讲平均复杂度分析方法那样,找出所有的输入情况及相应的发生概率,然后再计算加权平均值。

针对这种特殊的场景,引入了一种更加简单的分析方法:摊还分析法,通过摊还分析得到的时间复杂度我们起了一个名字,叫均摊时间复杂度

对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度就是一种特殊的平均时间复杂度


  • Post title:最好、最坏、平均、均摊时间复杂度
  • Post author:Varsion
  • Create time:2020-07-29 12:02:37
  • Post link:https://blog.varsion.cn/post/d0d6f34f.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments