Java数据结构之集合框架与常用算法有哪些

    1 集合框架1.1 集合框架概念

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

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

    类和接口总览:

    Java数据结构之集合框架与常用算法

    1.2 容器涉及的数据结构

    Collection:是一个接口,包含了大部分容器常用的一些方法

    List:是一个接口,规范了ArrayList 和 LinkedList中要实现的方法

    • ArrayList:实现了List接口,底层为动态类型顺序表

    • LinkedList:实现了List接口,底层为双向链表

    Stack:底层是栈,栈是一种特殊的顺序表

    Queue:底层是队列,队列是一种特殊的顺序表

    Deque:是一个接口

    Set:集合,是一个接口,里面放置的是K模型

    • HashSet:底层为哈希桶,查询的时间复杂度为O(1)

    • TreeSet:底层为红黑树,查询的时间复杂度为O( ),关于key有序的

    Map:映射,里面存储的是K-V模型的键值对

    • HashMap:底层为哈希桶,查询时间复杂度为O(1)

    • TreeMap:底层为红黑树,查询的时间复杂度为O( ),关于key有序

    2 算法2.1 算法概念

    算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。算法是由一系列计算步骤组成的,其目的在于将输入数据转化为输出结果。

    2.2 算法效率

    算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。随着计算机行业的急速发展,计算机的存储容量已经达到了相当高的水平。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

    3 时间复杂度3.1 时间复杂度概念

    时间复杂度是计算机科学中的一个数学函数,表示算法的运行时间,其定量描述了算法的时间效率。在理论上无法计算一个算法的执行时间,只有在将程序实际运行在计算机上之后才能得知其耗时。尽管每个算法都可以进行上机测试,但这样很繁琐,因此才有了通过时间复杂度进行分析的方式。算法的时间复杂度是基于其中语句执行次数的花费时间成正比例,时间复杂度取决于算法中基本操作的执行次数。

    3.2 大O的渐进表示法// 请计算一下func1基本操作执行了多少次?
    void func1(int N){
    int count = 0;

    for (int i = 0;
    i <
    N ;
    i++) {
    for (int j = 0;
    j <
    N ;
    j++) {
    count++;

    }
    }
    for (int k = 0;
    k <
    2 * N ;
    k++) {
    count++;

    }
    int M = 10;

    while ((M--) >
    0) {
    count++;

    }
    System.out.println(count);

    }

    Func1 执行的基本操作次数 :F(N)=N^2+2*N+10

    • N = 10 F(N) = 130

    • N = 100 F(N) = 10210

    • N = 1000 F(N) = 1002010

    实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

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

    3.3 推导大O阶方法
    • 用常数1取代运行时间中的所有加法常数。

    • 在修改后的运行次数函数中,只保留最高阶项。

    • 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

    使用大O的渐进表示法以后,Func1的时间复杂度为:O(n^2)

    • N = 10 F(N) = 100

    • N = 100 F(N) = 10000

    • N = 1000 F(N) = 1000000

    通过上述内容,我们可以看出大O渐进表示法排除了在结果上影响不大的项,从而简洁明确地表示了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况:

    最坏情况:任意输入规模的最大运行次数(上界)

    平均情况:任意输入规模的期望运行次数

    最好情况:任意输入规模的最小运行次数(下界)

    例如:在一个长度为N数组中搜索一个数据x

    最好情况:1次找到

    最坏情况:N次找到

    平均情况:N/2次找到

    在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

    4 空间复杂度

    对于一个算法而言,空间复杂度表示它在执行期间所需的临时存储空间大小。空间复杂度的计算方式并非程序所占用的字节数量,因为这并没有太大的意义;实际上,空间复杂度的计算基于变量的数量。大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:

    // 计算fibonacci的空间复杂度?
    int[] fibonacci(int n) {
    long[] fibArray = new long[n + 1];

    fibArray[0] = 0;

    fibArray[1] = 1;

    for (int i = 2;
    i <
    = n ;
    i++) {
    fibArray[i] = fibArray[i - 1] + fibArray [i - 2];

    }
    return fibArray;

    }

    实例3:

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

    }
    • 实例1使用了常数个额外空间,所以空间复杂度为 O(1)

    • 实例2动态开辟了N个空间,空间复杂度为 O(N)

    • 实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)



    一、集合框架
    Java集合框架是一个提供了多种数据结构和算法的类库,其中包括List(列表)、Set(集合)、Map(映射)等等。集合框架具有如下优点:
    1. 数据存储和访问都是非常高效的。
    2. 可以方便地进行数据结构的操作和算法的实现。
    3. 对于数据结构的模块化,可以让代码逻辑更加清晰,易于代码维护。
    本节将介绍Java集合框架中最常用的几种数据结构。
    1.1 List(列表)
    列表是Java集合框架中最常用的数据结构之一。它可以存储一系列的对象,并且每一个元素都有一个唯一的编号,这个编号被称为索引。在Java集合框架中,List接口有几个实现类,甚至可以根据访问方式的不同,形成不同的实现。
    1.2 Set(集合)
    Set是一个存储无序元素的集合。集合可以在插入和搜索元素时进行常数时间的操作。Set还可以提供一些关于元素的去重、查找和遍历等的操作。
    1.3 Map(映射)
    Map是一个将一个对象映射为另一个对象的集合。在Java集合框架中,Map是一个非常重要的数据结构。在Map中,每个元素由一个键和一个值组成,每个键与对应的值都是互相唯一(一个键对应一个值,一个值对应一个键)。
    二、常用算法
    除了集合框架以外,Java还提供了许多常用算法的实现,在Java中进行数据结构和算法的操作非常容易。本节将介绍Java中常用的几种算法。
    2.1 排序算法
    排序算法是熟悉的算法之一,Java提供了不同的排序算法实现,例如冒泡排序、快速排序、归并排序和选择排序等在Java中都可以进行实现。这些排序算法都具有很好的性能和可扩展性,以适应不同的场景需求。
    2.2 查找算法
    查找算法是在某个数据集合中进行元素搜索的算法。Java提供了许多常用的查找算法实现,例如二分查找、哈希表和树搜索等。这些算法都非常高效,可以在数据量较小的情况下,提高数据搜索的效率。
    2.3 图算法
    图算法是指对图数据结构执行的算法。Java提供了许多用于图算法的实现。如最短路径算法、最小生成树算法、深度优先搜索算法和广度优先搜索算法等。
    以上仅是Java的数据结构之集合框架与常用算法的一个部分介绍,Java还有许多其他的数据结构和算法,而在实践中,需要根据实际情况进行选择,在Java中进行数据结构和算法的操作,会使我们的编程能力大大提高。