【数据结构（一）】初识数据结构

04-14 1525阅读

❣博主主页: 33的博客❣

▶文章专栏分类: Java从入门到精通◀

🚚我的代码仓库: 33的代码仓库🚚

🫵🫵🫵关注我带你学更多数据结构知识

1.前言

数据结构是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合，从这篇文章开始，我们将一起进入数据结构的学习，那么该如何学好数据结构呢？博主的建议是多写代码，多思考，多画图！

本章重点

掌握数据结构基本知识主要包括集合框架，时间和空间复杂度，算法效率，大O渐进表示，包装类，泛型相关知识。

2.集合架构

Java 集合框架Java Collection Framework ，又被称为容器和其实现类classes 。

类和接口总览：

3.时间和空间复杂度

遇到一个算法，我们怎么衡量一个算法的好坏呢？

3.1算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。

3.2时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

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

最坏情况：任意输入规模的最大运行次数(上界)当说时间复杂度一般值最坏情况下

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

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

3.2.1大O的渐进表示

在计算时间复杂度时，我们不需要计算精确的执行次数，只需要大概的次数，那么我们就剋用大O渐进表示法去掉那些对结果影响不大的项，简明表示执行的次数。

规则：

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

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

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

3.2.2常见时间复杂度举例

例1.

void func2(int N) {
    int count = 0;
    for (int k = 0; k  0) {
        count++;	//时间复杂度10
    }
    System.out.println(count);
 }

时间复杂度2N+10 为O（N）

例2.

void func3(int N, int M) {
    int count = 0;
    for (int k = 0; k  
时间复杂度M+N为O（M+N） 
例3. 
// 计算func4的时间复杂度？
void func4(int N) {
    int count = 0;
    for (int k = 0; k  
时间复杂度100为O（1） 
例4. 
// 计算bubbleSort的时间复杂度？
void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i  array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true) {
            break;
        }
    }
 }
 
假设array.length=N,那么第一次循环执行N-1次，第二次循坏执行N-2次，第三次循环执行N-3…最后一次为1，那么总次数就是（N-1)+(N-2)+(N-3)+…1,等差数列求和结果为（NN-N）/2那么时间复杂度为O（NN）。 
例5. 
int binarySearch(int[] array, int value) {
    int begin = 0;
    int end = array.length - 1;
    while (begin 
        int mid = begin + ((end-begin) / 2);
        if (array[mid]  
那么剩下1个数就需要时间复杂度O（log2^N）。 
例6. 
// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
    return N  
递归复杂度=递归次数*每次递归后执行的次数
时间复杂度=（N-1）*1=O(N) 
例7. 
int fibonacci(int N) {
    return N  
3.3空间复杂度 
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。 
例1. 
void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--) {
        boolean sorted = true;
        for (int i = 1; i  array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
 
        if (sorted == true) {
            break;
        }
        }
       }
   //输出O（1）
 
例2. 
int[] fibonacci(int n) {
 long[] fibArray = new long[n + 1];
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i 
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
 }
 //O（N）

 Integer a = 127;
 Integer b = 127;
 Integer c = 128;
 Integer d = 128;
 System.out.println(a == b);//true
 System.out.println(c == d);//false
 }

    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);
    }
 }
//添加 
5.3泛型类的使用 
语法： 
泛型类 变量名; //定义一个泛型类引用
MyArray a;
new  泛型类(构造方法实参); // 示例化一个泛型类对象
MyArray myArray = new MyArray();
 
5.4泛型是如何编译 
在编译过程中将所有的T替换为object，这种机制称为擦除机制，在运行的时候并没有泛型的概念。
通过命令：javap -c 查看字节码文件，所有的T都是Object:
在编译的过程当中，将所有的T替换为Object这种机制，我们称为：擦除机制。
Java的泛型机制是在编译级别实现的。 
实例化的时候不能实例化一个泛型数组。 
T[] a=new T[5];//这样定义泛型是错误的，这个时候我们不知道到底定义的什么类型的数组
//以我们现在的知识，一般定义数组的时候，我们采取以下方式：
object[] a=new obje[5];
 
5.5泛型的上界 
在定义泛型类时，有时需要对传入的类型变量做一定的约束，可以通过类型边界来约束。
语法 
class 泛型类名称 {
    ...
 }
MyArray l1;        // 正常，因为 Integer 是 Number 的子类型
MyArray l2;     // 编译错误，因为 String 不是 Number 的子类型
 
5.6泛型方法 
定义语法： 
方法限定符  返回值类型 方法名称(形参列表) { ... }
 
示例： 
public class Util {
    //静态的泛型方法 需要在static后用声明泛型类型参数
    public static  void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
 }
 //使用
 Integer[] a = { ... };
 Util.swap(a, 0, 9);//使用类型推导
 Util.swap(a, 0, 9);//不使用类型推导
 
6.总结 
 
 本篇介绍数据结构基本知识主要包括集合框架，时间和空间复杂度，算法效率，大O渐进表示，包装类，泛型相关知识，其中关于用泛型定义数组的内容，博主比并没有深入讲解，感兴趣的同学可以查看其他博主的内容。 
 
下期预告：顺序表