什么是数据结构？

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

分类

逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图形结构

物理结构

逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

• 顺序结构
• 链式存储结构

什么是算法

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

算法分析

研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求

对时间进行分析就是时间复杂度分析，如果是空间就是空间复杂度分析

时间复杂度分析

事件分析估算

在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：

1. 算法采用的策略和方案；
2. 编译产生的代码质量：
3. 问题的输入规模（所谓的问题输入规模就是输入量的多少）
4. 机器执行指令的速度

public static void main(String[] args) {
    int sum = 0; //执行一次
    int n = 100; //执行一次
    for (int i = 1; i <= n; i++) { //执行N+1
        sum += i; //执行N次
    }
    System.out.println("总和="+sum);
}

public static void main(String[] args) {
    int sum = 0; //执行一次
    int n = 100; //执行一次
    sum = (n + 1) * n / 2; //执行一次
    System.out.println("总和="+sum);
}

算法最终就是核心操作的次数和输入规模关联起来。

大 0 计法

• 用常数1取代运行时间中的所有加法常数：
• 在修改后的运行次数中，只保留高阶项；
• 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；

案例一

执行了3次，大O表示：O(1)

public static void main(String[] args) {
    int sum = 0; //执行一次
    int n = 100; //执行一次
    sum = (n + 1) * n / 2; //执行一次
    System.out.println("总和="+sum);
}

案例二

执行了n+2次，大O表示：O(N)

public static void main(String[] args) {
    int sum = 0; //执行一次
    int n = 100; //执行一次
    for (int i = 1; i <= n; i++) { //执行N+1
        sum += i; //执行N次
    }
    System.out.println("总和="+sum);
}

案例三

执行了N^2+2，大O表示：O(N^2)

public static void main(String[] args) {
    int sum = 0; //执行一次
    int n = 100; //执行一次
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            sum += i;
        }
    }
}

函数调用事件分析

案例1

大O表示 O(N)，sout是随着for也就是N次

public static void main(String[] args) {
    int n = 100; //执行一次
    for (int i = 1; i <= n; i++) {
        sout();
    }
}
private static void sout() {
    System.out.println();
}

案例2

O(N^2)

    public static void main(String[] args) {
        int n = 100; //执行一次
        for (int i = 1; i <= n; i++) {
            sout();
        }
    }
    private static void sout() {
        for (int i = 0; i < 100; i++) {
            System.out.println(i);
            
        }
    }