数据结构与算法_1_概念

数据结构与算法

• • 数据结构初识
  • • 1、数据结构的定义
    • 2、数据结构的分类
  • 算法初识
  • • 1、定义
    • 2、算法分析
    • • 1、时间复杂度
      • 2、空间复杂度

数据结构初识

1、数据结构的定义

数据结构就是把数据元素按照一定的关系组合起来的集合，用来组织和存储数据。

2、数据结构的分类

逻辑结构（按照数据和数据之间的关系抽象出来）

1. 集合结构：集合结构中的数据元素除了属于同一个集合外，他们之间没有任何的关系
2. 线性关系：线性结构中的数据元素存在一对一的关系
3. 树形结构：树形结构中的数据存在一对多的层次关系
4. 图形结构：数据元素是多对多的关系

物理结构（按照数据在计算机上进行存储角度进行出发） ==》存储结构

1. 顺序存储结构：将元素顺序的放到连续的存储单元中，数据的逻辑结构和存储结构相一致
2. 链式存储结构：把数据元素放在任意的存储单元中，这组单元可以是连续的，也可是非连续的，此时数据之间不能反映元素的逻辑关系，因此在链式存储中引进了指针存储元素的地址，通过地址找到相关元素的位置。

算法初识

1、定义

根据一定的条件，对一些数据进行计算，得到需要的结果。

2、算法分析

==> 最终目的是如何花更少时间、占用更少内存去解决我们需要处理的问题，涉及到分析算法的时间复杂度、空间复杂度

1、时间复杂度

1、分析方式：

1、事后分析法：

/**
 * @author : jiang--
 * @date : 2021/6/1520:31
 * @Description :
 */
public class 时间复杂度分析 {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int sum = 0;
        for (int i = 0; i < 100000; i++) {
            sum += sum;
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
}

通过计算时间计算出算法时间  ==》  end - start

2、事前分析法

• **算法采用的策略和方案 **
• 编译产生的代码质量（编译器的问题）
• 问题的输入规模（输入量的大小）
• 机器执行的效率（服务器的问题）
  eg:1到100的和
  方案1：

static void test1() {
        long start = System.currentTimeMillis();
        int sum = 0;
        for (int i = 0; i < 100; i++) {
            sum += sum;
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

方案2：

static void test2() {
        int sum = 0;
        int n = 100;
        sum = (n + 1) * n / 2;
        System.out.println(sum);

    }

2、算法效率结论

• 算法函数中的常数可以忽略
• 算法函数中的最高次幂的常熟因子可以忽略
• 算法中的最高次幂越小，算法效率越高

3、时间复杂度表示方法 ---- 大O阶

输入次数为n：

• 算法1:3次 ------> O(1)
• 算法2:n+3次 ------> O(n)
• 算法1:n^2 + 3次 ------> O(n ^ 2)

常见的复杂度总结：

1. 常数级别 1
2. 对数级别 logN 二分策略、二分查找
3. 线性级别 N 循环
4. 线性对数级别 NlogN 分治思想
5. 平方级别 N^2 双层循环
6. 立方级别 N^2 三层循环
7. 指数级别 2^N 穷举查找

复杂度排序：
O(1)<O(logN)<O(NlogN )<( N^2)

2、空间复杂度

1、内存占用

1. 基本数据类型的内存占用：
   byte 1字节
   short 2字节
   int 4字节
   long 8字节
   float 4字节
   double 8字节
   boolean 1字节
   char 2字节

2. 计算机访问内存的方式：都是一次一个字节

3. 一个引用（机器地址）需要八个字节表示
   Date date = new Date（）中的date需要八个字节

4. 创建一个对象，除了Date（）中内部的成员属性占用的的内存外，还需要24个字节的头信息（16个自己对象的开销，四字节用于保存长度，四个填充字节）

5. 一般内存的使用，如果不够八个字节，都会呗自动填充为八个字节

6. java中的数组被限定为对象，他们一般会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24个字节的头信息（16个自己对象的开销，四字节用于保存长度，四个填充字节）

算法的空间复杂度

/**
 * @author : jiang--
 * @date : 2021/6/1521:48
 * @Description :
 */
public class a2空间复杂度 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
//         reverse(arr);
        reverse2(arr);
    }

//方法一
    static int[] reverse(int[] arr){
        int n = arr.length;//申请4字节
        int[] temp = new int[n];//申请4*N+24字节
        for (int i = 0; i < n; i++) {
            temp[i] = arr[n-i-1];
        }
        return temp;
    }
    
-------->     大O阶：O(1)

//方法二
    static int[] reverse2(int[] arr){
        int n = arr.length;//申请4字节
        int temp ;//申请4字节
        for (int i = 0; i < n/2; i++) {
            temp = arr[i];
            arr[i] = arr[n-1-i];
            arr[n-1-i] = temp;
        }
        return arr;
    }
}

-------->     大O阶：O(N)