专栏首页wfaceboss均摊复杂度和防止复杂度的震荡

均摊复杂度和防止复杂度的震荡

关于上一节中我们对添加操作的时间复杂度归结为O(n)是考虑了扩容操作(resize)在内的。就addLast(e)操作而言,时间复杂度为O(1),在考虑最坏情况下,每次添加均会触发扩容操作,需要移动n个元素,因此此时addLast操作的时间复杂度为O(n)。

(1)addLast(e)均摊时间复杂度分析

resize(n)   O(n)

 假设当前capacity=8,并且每一次添加操作都使用addLast方法

17次基本操作包括:9次添加操作,8次转移操作。均摊每次addLast操作进行大约两次基本操作:

平均值为:17/9≈ 2。

  假设capacity=n,n+1次addLast操作,触发resize,总共进行了2n+1=(n+1)+ n次基本操作;

  均摊每次addLast操作进行大约两次基本操作:

平均值为: 2n+1 / n+1 ≈ 2

结论:因此addLast均摊时间复杂度为O(1),均摊时间复杂度会比最坏情况有意义,因为一般情况下resize不会每一次都会触发,因此可以分摊到其他上面。 同理,removeLast操作均摊时间复杂度也是O(1)

(1)addLast(e)和removeLast(e)复杂度震荡分析

设数组的容量为n,此时数组中的个数为n个,此时我们向数组中添加一个元素,则会触发扩容操作;然后在从数组中删除一个元素时又会重新触发缩容操作,这样反复执行都会耗费O(n)的复杂度,导致复杂度震荡。

演示如下:

  第一次执行addLast(e)时间复杂度:O(n)

   第二次执行removeLast(e)时间复杂度:O(n)

  第三次执行addLast(e)时间复杂度:O(n)

 第四次执行removeLast(e)时间复杂度:O(n)

产生复杂度震荡的原因为:removeLast时resize过于着急(Eager)。

解决办法为:Lazy(remove延迟执行resize)

  容量2n,size=n+1时:

 容量2n,size=n时,进行缩容1/2:

 容量2n,size=1/4*2n,进行缩容1/2  :

当size==capacity/4时,才将capacity减半。

现在我们来进一步改进我们的程序代码:

   //从数组中删除index位置的元素,返回删除的元素
    public E remove(int index) {
        //1.判断索引的选择是否合法
        if (index < 0 || index > size)
            throw new IllegalArgumentException("您选择的位置不合法");

        //2.先存储需要删除的索引对应的值
        E ret = data[index];

        //将索引为index之后(index)的元素依次向前移动
        for (int i = index + 1; i < size; i++) {
            //3.执行删除--实质为索引为index之后(index)的元素依次向前移动,将元素覆盖
            data[i - 1] = data[i];
        }
        //4.维护size变量
        size--;
        // loitering objects != memory leak 手动释放内存空间
        data[size] = null;

        //缩容操作
        if (size == data.length / 4 && data.length != 0) {
            resize(data.length / 2);
        }
        //5.返回被删除的元素
        return ret;
    }

 到此我们完成了一个比较完善的动态数组的封装。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 封装数组之改进为泛型数组

    前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组...

    wfaceboss
  • 封装数组之添加元素

    在上一小节中,我们对数组进行了一个基本的封装,该小节中,我们在上一次基础上,新增往数组添加元素的方法:

    wfaceboss
  • 封装数组之实现在数组中查询元素和修改元素

    前言:在上一小节中,我们已经对如何往数组中添加一个元素的方法进行了编写,此节中我们就如何查询出数组中元素与修改元素的方法进行编写。

    wfaceboss
  • 【Python进阶】实战Python面向对象基本编程

    欢迎来到专栏《Python进阶》。在这个专栏中,我们会讲述Python的各种进阶操作,包括Python对文件、数据的处理,Python各种好用的库如NumPy、...

    用户1508658
  • 【每周一坑】乒乓数

    刚从假期回来,又要迎接周末,各位看官想必都很辛苦,所以本周每周一坑为大家准备一道简单的甜点题目,本题取材于伯克利大学 CS61 课程 homework02。 求...

    Crossin先生
  • 子串和

    给定一整型数列{a1,a2...,an},找出连续非空子串{ax,ax+1,...,ay},使得该子序列的和最大,其中,1<=x<=y<=n。

    书童小二
  • 高质量编码--使用Pandas和Tornado构建高性能数据查询服务

    大数情况下,数据保存在数据库中,使用SQL来从数据库中查询数据,但相对于直接从内存中取数据前者显得比较慢和笨重。下面介绍基于csv文件目录存储数据,使用Torn...

    MiaoGIS
  • iOS开发技巧篇

    在iOS开发中,有一些技巧可以提高程序猿的开发效率。 1,Xcode真机调试 Xcode 7推出之前,想要真机调试,iOS开发者必须花$99购买苹果开发者账号,...

    xiangzhihong
  • 用R语言实现对不平衡数据的四种处理方法

    在对不平衡的分类数据集进行建模时,机器学习算法可能并不稳定,其预测结果甚至可能是有偏的,而预测精度此时也变得带有误导性。那么,这种结果是为何发生的呢?到底是什么...

    小莹莹
  • 记录一下JSP得坑

    今天写作业,发现以前的EL表达式都用不了,页面会直接把EL表达式打印出来,后来问老师,他说要我重装老版本得myeclipse,但是我始终不想用老版本得,百度了一...

    用户1444933

扫码关注云+社区

领取腾讯云代金券