最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(1.9)均摊复杂度和防止复杂度的震荡

    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;
    }
    

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(1.9)均摊复杂度和防止复杂度的震荡

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 155会员总数(位)
    • 3735资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 382稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级