当前位置：首页 > news >正文

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

news 来源：原创 2024/9/20 12:33:24

1.前言

2.时间和空间复杂度

2.1算法效率

2.2时间复杂度

2.2.1概念

2.2.2大O渐进表示法

2.2.3推导大O阶方法

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

2.3空间复杂度

2.3.1概念

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

3.包装类

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

3.2装箱和拆箱

4.泛型

4.1概念

4.2引出泛型

4.3语法

5.泛型类的使用

5.1语法

5.2类型推导

6.泛型的上界

6.1概念

6.2语法

7.泛型方法

8.总结

1.前言

本篇将主要介绍数据结构的基本知识：时间和空间复杂度、算法效率、大O渐进表示法、包装类、泛型相关知识。

2.时间和空间复杂度

2.1算法效率

算法效率分析分为两种：第一种是 时间效率 ，第二种是 空间效率 。

时间效率被称为时间复杂度。

空间效率被称作空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

2.2时间复杂度

2.2.1概念

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

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

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