1 什么是数据结构？

数据结构是一门研究非数据计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科
数据结构是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据

2 数据结构分类

数据结构的分类

逻辑结构：是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类

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

物理结构：逻辑结构在计算机中真正的表达方式（又称映像）成为物理结构

• 顺序存储结构：数据元素放到地址连续的存储单元里面。其数据见的逻辑关系和物理关系是一致的
• 链式存储结构：数据严肃放在任意存储单元里面，存储单元可以是连续的也可以是不连续的。数据元素之间并不能反映元素间的逻辑关系。

3 什么是算法？

算法指解决方案的准确而完整的描述，是一系列解决问题的清晰指令
算法代表这用系统方法解决问题的策略机制，能够对一定规范的输入，在有限时间内获得所要求的输出

4 算法初体验

优秀的算法：

1. 花最少的时间完成需求
2. 占用最少的内存空间完成需求

5 算法分析

5.1 时间复杂度分析

高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：

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

一个程序的运行时间依赖于算法的好坏和问题的输入规模

5.1.1 函数渐进增长

1. 算法的常数操作可以忽略不计
2. 最高次项相乘的常数可以忽略
3. 最高次幂越小，算法效率越高

5.1.2 算大时间复杂度

大O记法

语句总的执行次数T(n)
算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))

时间复杂度：表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同
执行次数=执行时间

规则：

1. 用常数1取代运行时间中的所有加法常数
2. 再修改后的运行次数中，只保留最高阶
3. 如果最高阶项存在，且常数因子部位1，则去除这个项相乘的常数

线性阶

一般含有非嵌套循环涉及线性阶，线性阶随着输入规模的扩大，对应计算次数呈直线增长

package com.gtt.test;
public class Demo002 {
    public static void main(String[] args) {
        int sum=0;
        int n=100;
        for (int i=1;i<=n;i++){
            sum+=i;
        }
        System.out.println("sum="+sum); //sum=5050
    }
}

循环的时间复杂度为O(n)

平方阶

一般嵌套循环属于平方阶

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  16:53
 * @Description 平方阶
 */

public class Demo003 {
    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;
            }
        }
        System.out.println(sum);    //505000
    }
}

时间复杂度是O(n^2)

立方阶

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  16:55
 * @Description 立方阶
 */

public class Demo004 {
    public static void main(String[] args) {
        int x=0;
        int n=100;
        for (int i = 1; i <=n; i++) {
            for (int j = i; j <=n; j++) {
                for (int k = j; k <=n ; k++) {
                 x++;
                }
            }
        }
        System.out.println(x);  //171700
    }
}

时间复杂度是O(n^3)

对数阶

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  16:58
 * @Description 对数阶
 */

public class Demo005 {
    public static void main(String[] args) {
        int x=1;
        int n=100;
        while (x<n){
            x=x*2;
        }
        System.out.println(x); //128
    }
}

由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环
2^x=n
x=log(2)n
时间复杂度为O(logn)

常数项

不涉及循环操作的都是常数项

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  17:02
 * @Description 常数项
 */

public class Demo006 {
    public static void main(String[] args) {
        int n=100;
        int i=n+2;
        System.out.println(i); //102
    }
}

时间复杂度为O(1)

复杂程度从低到高依次为： O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)

5.1.3 函数调用的时间复杂度

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  17:09
 * @Description 函数调用的时间复杂度
 */

public class Demo007 {
    public static void main(String[] args) {
        int n=100;
        for(int i=0;i<n;i++){
            show(i);
        }
    }

    private static void show(int i) {
        System.out.println(i);
    }

}

show方法的时间复杂度为O(1)
main方法的时间复杂度就是O(n)

package com.gtt.test;

/**
 * @Author gett
 * @Date 2021/11/18  17:11
 * @Description 函数调用的时间复杂度
 */

public class Demo008 {
    public static void main(String[] args) {
        int n=100;
        for (int i = 0; i < n; i++) {
            show(i);
        }
    }

    private static void show(int i) {
        for (int j=0;j<i;i++){
            System.out.println(i);
        }
    }

}

show方法的时间复杂度为O(n)
main方法的时间复杂度为O(n^2)

5.1.4 最坏情况

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间

5.2 空间复杂度

5.2.1 Java内存

1. 计算机访问内存的方式是一次一个字节
2. 一个引用（机器地址）需要8个字节
3. 创建一个对象，每个对象自身开销是16个字节，用来保存对象头信息
4. 一般内存的使用，如果不够8个字节，会自动填充为8字节
5. 一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

5.2.2 算法的空间复杂度

估计大量程序的内存使用情况
算法的空间复杂度计算公式记作：S(n)=O(f(n)),其中n为输入规模，f(n)为语句关于n所占存储空间的函数。