首页 > 编程语言 >Java—集合框架、时间和空间复杂度

Java—集合框架、时间和空间复杂度

时间:2024-06-05 16:30:05浏览次数:35  
标签:end 递归 int 复杂度 空间 集合 Java array

一、集合框架

Java集合框架(Java Collection Framework),又称为容器(container),是定义在 java.util 包下的一组接口(interfaces)和其实现类(classes)

其主要表现为将多个元素(element)置于一个单元中,用于对这些元素进行快速、便捷的存储(store)、检索(retrieve)、管理(manipulate),即俗称的增删查改(CRUD)

类和接口总览

二、时间和空间复杂度

1、概念:

分析算法效率有两种方式:一是时间效率,二是空间效率。时间效率被称为时间复杂度,而空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行时间,而空间复杂度主要衡量一个算法所需要的额外空间

2、时间复杂度

算法中的基本操作的执行次数,为算法的时间复杂度

一般用大O的渐进表示法来表示时间复杂度

大O符号(Big O notation):用来描述函数渐进行为的数学符号

推导大O阶的方法

  • 1、用常数1取代运行时间中的所有加法常数
  • 2、在修改后的运行次数函数中,只保留最高阶项
  • 3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数,从而得到大O阶

示例1:

// 计算bubbleSort的时间复杂度?
void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
 
        if (sorted == true) {
            break;
        }
    }
 }

解析:


示例2: 

// 计算binarySearch的时间复杂度?
int binarySearch(int[] array, int value) {
    int begin = 0;
    int end = array.length - 1;
    while (begin <= end) {
        int mid = begin + ((end-begin) / 2);
        if (array[mid] < value)
            begin = mid + 1;
        else if (array[mid] > value)
            end = mid - 1;
        else
            return mid;
    }
 
    return -1;
 }

解析:


示例3:

// 计算阶乘递归factorial的时间复杂度?
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
 }

 解析:不普适的计算方式:递归的时间复杂度 = 递归的次数 * 每次递归执行的次数

该代码基本操作递归了N次,时间复杂度为O(N)


示例4:

// 计算斐波那契递归fibonacci的时间复杂度?
int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
 }

解析:

 3、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,也采用大O渐进表示法

示例1:

    // 计算bubbleSort的空间复杂度?
    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }

            if (sorted == true) {
                break;
            }
        }
    }

解析:

使用了 end、sorted、i 三个常数个额外空间,所以空间复杂度为O(1)


示例2:

    //计算fibonacci的空间复杂度
    long[] fibonacci(int n) {
        long[] fibArry = new long[n+1];
        fibArry[0] = 0;
        fibArry[1] = 1;
        for (int i = 2; i <= n; i++) {
            fibArry[i] = fibArry[i-1] + fibArry[i-2];
        }
        return fibArry;
    }

解析:

要求n项的斐波那契数,把他们都存放到额外开辟的数组空间中,动态开辟了N个空间,空间复杂度为O(N)


示例3:

// 计算阶乘递归Factorial的空间复杂度?
long factorial(int N) {
     return N < 2 ? N : factorial(N-1)*N;
 }

解析:

看递归了多少次,递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间,空间复杂度为O(N)

复杂度大小关系:

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2)

标签:end,递归,int,复杂度,空间,集合,Java,array
From: https://blog.csdn.net/Yuan_o_/article/details/139449834

相关文章

  • JavaDoc生成文档
    javaDoc命令是用来生成自己API文档的参数信息:@auchor:作者名@version:版本号@since:指明需要最早使用的jdk版本@param:参数名@return:返回值情况@throws:异常抛出情况//主要生成的参数如:/***@author林伟填*@version1.0*@since1.8*/publiccla......
  • Java (MyBatis)
    前沿MyBatis是一个开源的持久层框架,它简化了数据库访问的过程,通过将SQL语句和Java方法进行映射1.SQL和Java方法的映射:MyBatis使用XML或注解来配置SQL语句,并将SQL语句映射到Java接口或方法上,使得开发者可以直接调用Java方法来执行数据库操作。2.SQL语句的......
  • Java基于SSM的医院医患管理系统设计实现
    21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管理工作的重要性已逐渐被人们所认识,科学化的管理,使信息存储达到准确、快速、完善,并能提高工作管理效率,促进其发展。论文主要是对医院医患管......
  • Java基于SSM的员工信息管理系统设计实现
    现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本龙腾公司员工信息管理系统就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数据信息,使用这种软件工具可以帮助管理人员提高......
  • Java基于SSM的图书管理系统设计实现
    现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本图书管理系统就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数据信息,使用这种软件工具可以帮助管理人员提高事务处理效率,......
  • Java基于SSM的在线购物系统设计实现
    随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势:对于在线购物系统当然也不能排除在外,随着网络技术的不断成熟,带动了在线购物系统,它彻底改变了过去传统的管理方式,不仅使服务管理难度变低了,还提升了管理的灵活性。这种个性化的平......
  • java8新特性
    1.使用lambda表达式对集合进行迭代/***Lambda表达式遍历集合*/@TestpublicvoidlambdaTest1(){List<String>features=Arrays.asList("Lambdas","DefaultMethod","StreamAPI","DateandTimeAPI");......
  • JAVA:实际工作中,项目上线——打包war,并部署到Tomcat中运行(史上最详细教程)
    每日一讲希望每天叫醒你的不是闹钟,而是梦想!目录每日一讲1.部署原因1.1Tomcat介绍 2.Tomcat下载及安装2.1Tomcat下载2.2Tomcat在IDEA上部署​2.3解决Tomcat乱码问题3.打包war文件,并在Tomcat目录下运行3.1打包文件3.2Tomcat环境配置3.3Tomcat运行1.部署原因......
  • 【JS】JavaScript编程语言-谷歌浏览器调试之前端代码(2024-06-05)
    1、在浏览器中调试调试是指在一个脚本中找出并修复错误的过程。所有的现代浏览器和大多数其他环境都支持调试工具——开发者工具中的一个令调试更加容易的特殊用户界面。它也可以让我们一步步地跟踪代码以查看当前实际运行情况。在这里我们将会使用Chrome(谷歌浏览器)。2......
  • 集合的使用
    集合特性,元素唯一,不可重复,可以去重s=print(s)通过集合进行去重lists=[1,2,2,2,5,1,1,2,3,3,5,6,5,6,4]s=set(lists)print(s)遍历查询foriins:print(i)删除集合方法一del函数print(s)del(s)print(s)方法二remove函数s.remove(1)print(s)集合增加s.add......