• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(1.9)均摊复杂度和防止复杂度的震荡

极客笔记 Geekerstar 12个月前 (05-07) 583次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

resize的复杂度分析

之前的时间复杂度分析我们都是分析最坏的情况。

在最坏的情况下,我们addLast了,添加一个元素的同时也要进行扩容。

由于扩容是个O(n)级别的复杂度,这就使得整个操作的复杂度依然是O(n)级别的。

但是我们又不可能每次添加的时候都触碰到resize操作。

假设我们数组中有十个空间,要添加满十个元素之后才会触发resize操作,然后我们数组空间会变成20,此时我们要再添加十个元素才会再触发resize……以此类推。

那么此时我们应该怎么分析addLast时间复杂度呢?

以上案例,共9次addLast操作,然后会触发resize,8次元素转移的操作,总共进行了17次操作,这样来看的话:

于是得出结论:

均摊复杂度 amortized time complexity

均摊复杂度是一个相对比较耗时的操作,我们能保证不会每次都触发的话,那么这个相应的时间是可以分摊到其他的操作中的

复杂度震荡

但是当我们同时看addLast和removeLast操作,出现了一个问题,这个问题通常叫做复杂度震荡:

假设现在有一个数组,容量是n,并且现在已经装满了元素。

此时再调用addLast操作,添加一个新的元素,显然就需要扩容了。

扩容的过程会耗费O(n)的时间,之后马上进行removeLast操作。

根据之前的逻辑,由于扩容了,那现在的容量相当于就变成了2n。

现在又把刚刚添加的元素删除,在删除之后,现在这个数组的元素数是n,n是2n的二分之一。

所以此时对于remove这个操作,我们触发了缩容的过程,也就是又要调用一遍resize,时间复杂度依然是O(n)。

假如又添加一个元素,再调用addLast,重复了之前的过程。

现在由于容积是n,又要扩容成2n,此时时间复杂度是O(n),之后再进行删除操作……

之前说过,调用addLast和removeLast都是要隔n个操作再resize,而不会每次都触发resize。

但是现在我们制造了一个情景,存在每一次都耗费O(n)复杂度的情况,这就是复杂度的震荡。对于这个问题应该怎么解决呢?

解决方案是:使用相对懒惰一些的策略,当前数组,初始的时候是空的。

当我们填满了,此时再添加一个元素,就需要扩容了。

关键在于,当我们删除一个元素的时候,此时数组中容积的数量是容器的二分之一了。

不着急现在就进行缩容,而是再等等。

如果后面一直有删除操作的话,删除到整个数组的四分之一了,此时再进行缩容,但是只缩容数组的二分之一。

代码演示

结合上述所说,我们来修改一下之前的代码,其实很简单,只需要在remove中稍微修改一下就行了,如下所示:

public E remove(int index){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    E ret = data[index];
    for(int i = index + 1 ; i < size ; i ++)
        data[i - 1] = data[i];
    size --;
    data[size] = null; // loitering objects != memory leak

    if(size == data.length / 4 && data.length / 2 != 0)
        resize(data.length / 2);
    return ret;
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(1.9)均摊复杂度和防止复杂度的震荡
喜欢 (2)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00