【数据结构】初识数据结构

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 执行的基本操作次数：

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要 大概执行次数，那么这里我们 使用大 O 的渐进表示法（大O 符号（ Big O notation) ：是用于描述函数渐进行为的数学符号）

2.2.3推导大O阶方法

1 、用常数 1 取代运行时间中的所有加法常数。

2 、在修改后的运行次数函数中，只保留最高阶项。

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

使用大O的渐进表示法以后，Func1的时间复杂度为：

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大O阶的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行的次数。

另外，有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

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

最好情况： 1 次找到

最坏情况： N 次找到

平均情况： N/2 次找到

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

2.2.4常见时间复杂度计算举例

例1：计算func2的时间复杂度？

    void func2(int N) {
        int count = 0;
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
    }

例1基本操作执行了2N+10次，通过推导大O阶方法知道，它的时间复杂度为 O(N)。

例2：计算func3的时间复杂度？

    void func3(int N, int M) {
        int count = 0;
        for (int k = 0; k < M; k++) {
            count++;
        }
        for (int k = 0; k < N; k++) {
            count++;
        }
        System.out.println(count);
    }

例 2 基本操作执行了 M+N 次，有两个未知数 M 和 N ，时间复杂度为 O(N+M)。

例3：计算func4的时间复杂度？

void func4(int N) {
        int count = 0;
        for (int k = 0; k < 100; k++) {
            count++;
        }
        System.out.println(count);
    }

例 3 基本操作执行了 100 次，通过推导大 O 阶方法，时间复杂度为 O(1)。

例4：计算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;
            }
        }
    }

例 4 基本操作执行最好 N 次，最坏执行了 (N*(N-1))/2 次，通过推导大 O 阶方法 + 时间复杂度一般看最坏，时间复杂度为 O(N^2)。

例5：计算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;
    }

例5基本操作最好执行1次，最坏log₂N次，因为二分查找每次都会排除掉一半的不适合值，则每一次值都为上一次的1/2，所以当存在N个数据时，有总个数N/(2^(砍一半的次数)y) = 1(最后剩下的一个数) ==> y = log₂N,则时间复杂度为O(log₂N)。

例6： 计算阶乘递归factorial的时间复杂度？

long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;
    }

例6通过计算分析发现基本操作递归了N次，且递归的时间复杂度=递归次数*每次递归后的执行次数，则时间复杂度为O(N)。

例7： 计算斐波那契递归fibonacci的时间复杂度？

int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

例 7 通过计算分析发现基本操作递归了2^n次，时间复杂度为O( 2^N)。

2.3空间复杂度

2.3.1概念

空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度。
空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大 O 渐进表示法 。

2.3.2常见空间复杂度计算举例

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

例1使用了常数个额外空间，所以空间复杂度为O(1)。

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

例 2 动态开辟了 N 个空间，空间复杂度为O(N)。

例3：计算阶乘递归Factorial的空间复杂度？

long factorial(int N) {
        return N < 2 ? N : factorial(N - 1) * N;
    }

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

3.包装类

在 Java 中，由于基本类型不是继承自 Object ，为了在泛型代码中可以支持基本类型， Java给每个基本类型都对应了一个包装类型。

3.1基本数据类型和对应的包装类

注：除了 Integer 和 Character，其余基本类型的包装类都是首字母大写。

3.2装箱和拆箱

    int i = 10;
    // 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中
    Integer ii = Integer.valueOf(i);
    Integer ij = new Integer(i);
    // 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中
    int j = ii.intValue();

4.泛型

4.1概念

泛型是 适用于许多许多类型 。从代码上讲，就是对类型实现了参数化。

4.2引出泛型

实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据 成员方法 返回数组中某个下标的值。

class MyArray {
    public Object[] array = new Object[10];
    public Object getPos(int pos) {
        return this.array[pos];
    }
    public void setVal(int pos,Object val) {
        this.array[pos] = val;
    }    
 }
 public class TestDemo {
    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        myArray.setVal(0,10);
        myArray.setVal(1,"hello");//字符串也可以存放
        String ret = myArray.getPos(1);//编译报错
        //强行转化
        String ret =(String)myArray.getPos(1);
        System.out.println(ret);
    }
 }

通过运行上面的代码我们可以发现以下的问题：

1. 任何类型数据都可以存放。

2. 1 号下标本身就是字符串，但是确编译报错。必须进行强制类型转换。

因此在更多情况下，我们希望它只能够持有一种数据类型。而不是同时持有这么多类型。 所以泛型的主要目的：就是指定当前的容器，要持有什么类型的对象。让编译 器去做检查。此时，就需要把类型，作为参数传递。需要什么类型，就传入什么类型。

4.3语法

class MyArray<T> {//添加< >表示这个类是泛型
    public T[] array = (T[])new Object[10];//这句代码是错误的，这样写只是为了不让编译器报错
    public T getPos(int pos) {
        return this.array[pos];
    }
    public void setVal(int pos,T val) {
        this.array[pos] = val;
    }
 }
 public class TestDemo {
    public static void main(String[] args) {
        MyArray<Integer> myArray = new MyArray<>();
        //传入<Integer>后，每次存储数据时会检查存入的数据是不是我传入的类型，获取数据的时候也不需要强制转化。
        myArray.setVal(0,10);
        myArray.setVal(1,12);
        int ret = myArray.getPos(1);
        System.out.println(ret);
        myArray.setVal(2,"bit");
    }
 }

对上面代码进行解释：

1. 类名后的 <T> 代表占位符，表示当前类是一个泛型类。

了解： 【规范】类型形参一般使用一个大写字母表示，常用的名称有：

E 表示 Element
K 表示 Key
V 表示 Value
N 表示 Number
T 表示 Type
S, U, V 等等 - 第二、第三、第四个类型

2. 注释1处，不能new泛型类型的数组

意味着：T[] ts = new T[5];//是不对的

3. 注释 2 处，类型后加入 <Integer> 指定当前类型

4. 注释 3 处，不需要进行强制类型转换

5. 注释 4 处，代码编译报错，此时因为在注释 2 处指定类当前的类型，此时在注释 4 处，编译器会在存放元素的时候帮助我们进行类型检查。

5.泛型类的使用

5.1语法

泛型类<类型实参> 变量名; // 定义一个泛型类引用
new 泛型类<类型实参>(构造方法实参); // 实例化一个泛型类对象

举个例子：

MyArray<Integer> list = new MyArray<Integer>();

注意：泛型只能接受类，所有的基本数据类型必须使用包装类！

5.2类型推导

类型推导即当编译器可以根据上下文推导出类型实参时，可以省略类型实参的填写。

MyArray<Integer> list = new MyArray<>(); // 可以推导出实例化需要的类型实参为 Integer

6.泛型的上界

6.1概念

泛型的上界：在定义泛型类时，有时需要对传入的类型变量做一定的约束，可以通过类型边界来约束。

6.2语法

class 泛型类名称<类型形参 extends 类型边界> {
...
}

举个例子：

public class MyArray<E extends Number> {
...
}

MyArray<Integer> l1; // 正常，因为 Integer 是 Number 的子类型
MyArray<String> l2; // 编译错误，因为 String 不是 Number 的子类型

tips： 没有指定类型边界 E，可以视为 E extends Object

7.泛型方法

泛型方法定义语法：

方法限定符 <类型形参列表> 返回值类型方法名称(形参列表) { ... }

下面举个例子给大家看看：

public class Util {
    //静态的泛型方法 需要在static后用<>声明泛型类型参数
    public static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

8.总结

以上内容让大家能够初步认识数据结构的一些基本知识，后面还将继续与大家分享数据结构中的顺序表、链表、栈、队列、二叉树等内容，小欣建议大家在学数据结构的时候多画图、多动手与思考，才能更好地学习数据结构！

原文地址：https://blog.csdn.net/m0_74336101/article/details/140548905

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：STM32CubeIDE（低功耗模式）
下一篇：Sublime Text：跨平台高效代码编辑器之选

K-means 算法、层次聚类、密度聚类对鸢尾花（Iris）数据进行聚类
K-Means：适合规则分布的大规模数据，快速聚类。层次聚类：适合小规模数据和需要层次结构的场景，如基因分析或市场细分。DBSCAN：适合处理复杂形状簇和含有噪声的数据，如地理空间数据或异常检测。距离
阅读更多2024-10-18
CI/CD（持续集成与持续交付）流水线
通过这些步骤，你可以配置一个集成了 Jenkins、GitLab Webhook、Nexus 和 RabbitMQ 的完整 CI/CD 流水线。集成 Jenkins、GitLab Webhook、Ne
阅读更多2024-10-18
离大谱！现在用Ai做写真都这么成熟了？AI绘画SD零成本制作影楼级人像写真教程，AI变现副业指南！
首先什么是AI写真，顾名思义的话可以说成是用AI生成写真照（这里我们使用的是开源免费的Stable Diffusion，简称SD），我们先暂且这么理解，后面会从第一性原理来讲明白更深层次的AI写真概念
阅读更多2024-10-18
Qt-系统处理鼠标相关事件(57)
Qt-系统处理鼠标相关事件的使用
阅读更多2024-10-18
Kaggle Python练习：字符串和字典（Exercise: Strings and Dictionaries）
enumerate() 是 Python 的一个内置函数，用于为可迭代对象（如列表、元组或字符串）提供一个自动计数器，同时遍历该对象。它返回一个包含索引和值的迭代器，常用于 for 循环中。（我们鼓励
阅读更多2024-10-18
LeetCode：LCP77.符文储备（排序 Java）
比较简单，排序，然后找出连续的最长值即可。
阅读更多2024-10-18
数据泄露危机：提升文件安全意识的紧迫性
因此,提升文件安全意识,加强数据保护措施,已成为企业管理中不可忽视的重要议题。在数据泄露威胁日益严峻的今天,提升文件安全意识并采取有效的管理措施已成为企业的当务之急。通过构建全面的文件安全管理体系,并
阅读更多2024-10-18
[C++刷题] 基础小知识点(1) 乘方函数pow()
[C++刷题] 基础小知识点(1) 乘方函数 pow pow()
阅读更多2024-10-18
Nature正刊！伯明翰大学和牛津大学等研究人员解锁全球森林树木在减缓气候变化中的新角色！
随着全球气候变化的加剧，甲烷作为一种重要的温室气体，其在大气中的作用日益受到关注。尽管甲烷的排放源和吸收机制已有一定的研究，但树木在甲烷循环中的具体角色仍存在较大不确定性。传统观点认为，湿地和部分高地
阅读更多2024-10-18
【无人机设计与控制】基于极光优化算法PLO的多无人机协同三维路径规划
本文提出了一种基于极光优化算法（PLO）的多无人机协同三维路径规划方法，旨在解决复杂环境中的路径规划问题。通过引入极光优化算法，多个无人机能够在障碍环境中实现协同路径规划，确保飞行路径最短且安全，避免
阅读更多2024-10-18