Java均摊复杂度和防止复杂度的震荡原理分析

本文实例讲述了Java均摊复杂度和防止复杂度的震荡。分享给大家供大家参考，具体如下：

关于上一节封装数组的简单复杂度分析方法中我们对添加操作的时间复杂度归结为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;
  }

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

更多关于java相关内容感兴趣的读者可查看本站专题：《Java数组操作技巧总结》、《Java字符与字符串操作技巧总结》、《Java数学运算技巧总结》、《Java数据结构与算法教程》及《Java操作DOM节点技巧总结》

希望本文所述对大家java程序设计有所帮助。

赞 (0)

相关推荐

  • 史上最全的java随机数生成算法分享

    史上最全的java随机数生成算法分享

    复制代码 代码如下: String password = RandomUtil.generateString(10); 源码如下: 复制代码 代码如下: package com.javaniu.core.util;import java.util.Random;public class RandomUtil { public static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS

  • Java封装数组之改进为泛型数组操作详解

    本文实例讲述了Java封装数组之改进为泛型数组操作.分享给大家供大家参考,具体如下: 前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组. 1.定义泛型数组相关概念 (1)泛型数组让我们可以存放任何数据类型 (2)存放的类型不可以是基本数据类型,只能是类对象 基本类型: boolean.byte.char.short.int.long.float.double (3)每个基本数据类型都有

  • Java针对封装数组的简单复杂度分析方法

    本文实例讲述了Java针对封装数组的简单复杂度分析方法.分享给大家供大家参考,具体如下: 完成了数组的封装之后我们还需对其进行复杂度分析: 此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否. 1.简单概念 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂

  • 使用java数组 封装自己的数组操作示例

    本文实例讲述了使用java数组 封装自己的数组操作.分享给大家供大家参考,具体如下: 今天感冒了,全身酸软无力,啥样不想做,就来学习吧,此节我们从初步使用java中提供的数组,然后分析相关情况,过渡到封装我们自己的数组. 一.我们先来感受一下java提供的数组,以整型数组(int[])为例,相关代码如下: public class Main { public static void main(String[] args) { int[] arr = new int[10]; for(int i

  • Java封装数组之添加元素操作实例分析

    本文实例讲述了Java封装数组之添加元素操作.分享给大家供大家参考,具体如下: 在上一小节中,我们对数组进行了一个基本的封装,该小节中,我们在上一次基础上,新增往数组添加元素的方法: 1.向所有元素后添加一个元素 思路: (1)先判断当前数组容量是否已满,未满则转入(2),否则抛出异常 (2)在元素下标为size的位置插入新元素 (3)维护我们的size值 //向所有元素后添加元素 public void addLast(int e) { if (size == data.length) thr

  • Java封装数组实现包含、搜索和删除元素操作详解

    本文实例讲述了Java封装数组实现包含.搜索和删除元素操作.分享给大家供大家参考,具体如下: 前言:在上一小节中我们已经会了如何获取和如何修改数组中的元素,在本小节中我们将继续学习如何判断某个元素是否在数组中存在.查询出某个元素在数组中的位置.以及删除数组中元素等方法的编写. 1.查找数组中是否包含元素e,返回true或false //查找数组中是否包含元素e public boolean contains(int e) { for (int i = 0; i < size; i++) { if

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • Java封装数组之动态数组实现方法详解

    本文实例讲述了Java封装数组之动态数组实现方法.分享给大家供大家参考,具体如下: 前言:在此之前,我们封装的数组属于静态数组,也即数组空间固定长度,对于固定长度的数组当元素超过容量时会报数组空间不足.为了能更好的使用数组,我们来实现一个可以自动扩充容量的数组. 实现思路: 1.当数组容量达到事先定义值时创建一个空间是data数组两倍的newData数组(扩容): 2.把data数组中的元素全部赋值到newData数组中: 3.把data数组重新执行newData数组. 一.定义核心扩容方法 /

  • Java封装数组实现在数组中查询元素和修改元素操作示例

    本文实例讲述了Java封装数组实现在数组中查询元素和修改元素操作.分享给大家供大家参考,具体如下: 前言:在上一小节中,我们已经对如何往数组中添加一个元素的方法进行了编写,此节中我们就如何查询出数组中元素与修改元素的方法进行编写. 在数组中,数据是存储在私有变量data中的,若我们想知道打印输出一些关于data中数据相关信息,我们可以使用toString()方法,在java中,该方法需要每个类自定义重写实现,针对该类,自定义如下: @Override public String toString

  • Java均摊复杂度和防止复杂度的震荡原理分析

    本文实例讲述了Java均摊复杂度和防止复杂度的震荡.分享给大家供大家参考,具体如下: 关于上一节封装数组的简单复杂度分析方法中我们对添加操作的时间复杂度归结为O(n)是考虑了扩容操作(resize)在内的.就addLast(e)操作而言,时间复杂度为O(1),在考虑最坏情况下,每次添加均会触发扩容操作,需要移动n个元素,因此此时addLast操作的时间复杂度为O(n). (1)addLast(e)均摊时间复杂度分析 resize(n)   O(n) 假设当前capacity=8,并且每一次添加操

  • Java基于余弦方法实现的计算相似度算法示例

    本文实例讲述了Java基于余弦方法实现的计算相似度算法.分享给大家供大家参考,具体如下: (1)余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性.0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1.从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向.所以,它通常用于文件比较. 相关介绍可参考百度百科:余弦相似性 (2)算法实现的中未使用权重(IDF ---逆文档频率),使用词项的出现次数作为向量空间的值. import java.util.H

  • Java 动态代理原理分析

    Java 动态代理原理分析 概要 AOP的拦截功能是由java中的动态代理来实现的.说白了,就是在目标类的基础上增加切面逻辑,生成增强的目标类(该切面逻辑或者在目标类函数执行之前,或者目标类函数执行之后,或者在目标类函数抛出异常时候执行.Spring中的动态代理是使用Cglib进行实现的.我们这里分析的是JDK中的动态代理实现机制. 下面我们通过例子快速了解JDK中的动态代理实现方式. 示例 需要代理的接口 public interface IHello { public void sayHel

  • java 中volatile和lock原理分析

    java 中volatile和lock原理分析 volatile和lock是Java中用于线程协同同步的两种机制. Volatile volatile是Java中的一个关键字,它的作用有 保证变量的可见性 防止重排序 保证64位变量(long,double)的原子性读写 volatile在Java语言规范中规定的是 The Java programming language allows threads to access shared variables (§17.1). As a rule,

  • java 中ThreadPoolExecutor原理分析

    java 中ThreadPoolExecutor原理分析 线程池简介 Java线程池是开发中常用的工具,当我们有异步.并行的任务要处理时,经常会用到线程池,或者在实现一个服务器时,也需要使用线程池来接收连接处理请求. 线程池使用 JDK中提供的线程池实现位于java.util.concurrent.ThreadPoolExecutor.在使用时,通常使用ExecutorService接口,它提供了submit,invokeAll,shutdown等通用的方法. 在线程池配置方面,Executor

  • Java局部变量线程安全原理分析

    Java局部变量线程安全原理分析

    这篇文章主要介绍了Java局部变量线程安全原理分析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 方法调用栈结构: 每个线程都有自己独立的方法调用栈: 这种局部变量不共享,从而保证线程安全的技术,称为线程封闭技术. 案例:数据库连接池.采用线程封闭技术,线程获取的数据库连接connection,是独立的,在这个线程在关闭获取的这个connection之前,不会再分配给其他线程. 思考:递归调用太深,可能导致栈溢出. 栈溢出原因: 因为每调用一个

  • Java后台防止客户端重复请求、提交表单实现原理

    这篇文章主要介绍了Java后台防止客户端重复请求.提交表单实现原理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前言 在Web / App项目中,有一些请求或操作会对数据产生影响(比如新增.删除.修改),针对这类请求一般都需要做一些保护,以防止用户有意或无意的重复发起这样的请求导致的数据错乱. 常见处理方案 1.客户端 例如表单提交后将提交按钮设为disable 等等方法... 2.服务端 前端的限制仅能解决少部分问题,且不够彻底,后端自有的

  • Java Servlet 运行原理分析

    1 Servlet基本执行过程 Web容器(如Tomcat)判断当前请求是否第一次请求Servlet程序 . 如果是第一次,则Web容器执行以下任务: 加载Servlet类. 实例化Servlet类. 调用init方法并传入ServletConfig对象 如果不第一次执行,则: 调用service方法,并传入request和response对象 Web容器在需要删除Servlet时(例如,在停止服务器或重新部署项目时)将调用destroy方法. 2 Web容器如何处理Servlet请求 Web容

  • Java HashMap实现原理分析（一）

    从本文开始,介绍一下最常用的一个集合对象HashMap,HashMap存储的是键值对,本文采用的基于JDK11的源码实现. 一般大家都知道HashMap是通过put操作把一组键值对(key和value)存储到HashMap中,然后可以通过get(key)去获取key对应的value.而最重要的这两个过程是怎么实现的呢?下面我们就来对put和get这两个过程做一个分析. HashMap基本工作原理 下面先看一段源码: /** * The table, initialized on first us

  • Java cglib动态代理原理分析

    本文分下面三个部分来分析cglib动态代理的原理. cglib 动态代理示例 代理类分析 Fastclass 机制分析 一.cglib 动态代理示例 public class Target{ public void f(){ System.out.println("Target f()"); } public void g(){ System.out.println("Target g()"); } } public class Interceptor implem

随机推荐