废fa不多说，直接上货。

复杂度

评估算法优劣的核心指标：
​ 1.时间复杂度（算法流程决定）
​ 2.额外空间复杂度（算法流程决定）
​ 3.常数项时间（实现细节决定）

时间复杂度

常见的常数时间的操作

常见的算术运算(+、 -、x*、/、%等)常见的位运算(>>、 >>>、<<、|、&、^等)赋值、比较、自增、自减操作等.数组寻址操作总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。

时间复杂度就是程序中有多少常数时间操作。
当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉。
时间复杂度的意义在于:

当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的;每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。这就是时间复杂度的意义，它是衡量算法流程的复杂程度的-种指标，该指标只与数据量有关，与过程之外的优化无关

额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。作为输入参数的空间，不算额外空间。作为输出结果的空间，也不算额外空间。因为这些都是必要的、和现实目标有关的。所以都不算。但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

常数项时间

时间复杂度这个指标，是忽略低阶项和所有常数系数的。当两个流程的时间复杂度一样的时候，就需要比较常数项时间，简称拼常数项
比拼常数项方式：
放弃理论分析，生成随机数据直接测。
为什么不去理论分析?
不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。
比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。
所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。直接使用大量的随机数据然后测试运行时间俩做比拼

算法最优解：

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。
一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。

数据结构

线性结构

1)线性结构作为最常用的数据结构，其特点是数据元素之间存在一对-的线性关系2)线性结构有两 种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的3)链式存 储的线性表称为链表，链表中的存储元素不-定是连续的，元素节点中存放数据元素以及相邻元素的地

址信息
4)线性结构常见的有:数组、队列、链表和栈

非线性结构

非线性结构包括:二维数组，多维数组，广义表，树结构，图结构

数组

手撕一维数组的基本操作（增删改）

对新手非常友好！！！！

import java.util.Arrays;//import com.sun.tools.javac.code.Attribute.Array;public class MyArrayList {private static final int DEFAULT_CAPACITY = 10;int size;int length;int[] elements;public MyArrayList() {elements = new int[DEFAULT_CAPACITY];}    //------------------------------------------------//添加元素public void add(int e) {if(size == elements.length) {resize();}elements[size] = e;size++;}private void resize() {//扩容length = elements.length;length = length + (length>>1);elements = Arrays.copyOf(elements, length);}//------------------------------------------------//根据下标获取元素public int get(int index) {if(index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("数组越界");}return elements[index];}//------------------------------------------------//根据下标修改数组元素的值public void set(int index,int e) {if(index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("数组越界");}elements[index] = e;}    //------------------------------------------------//删除某个索引处的元素public void remove(int index) {if(index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("数组越界");}if(index == size-1) {elements[index] = 0;size--;return;}System.arraycopy(elements, index+1, elements, index, size-index-1);size--;}//------------------------------------------------//在指定索引处插入指定元素//add(int index,Object element)public void add(int index,int e) {if(index < 0 || index > size) {throw new ArrayIndexOutOfBoundsException("数组越界");}if(size == elements.length) {resize();}//元素组索引以后的元素都依次往后移动一位System.arraycopy(elements, index, elements, index+1, size-index);elements[index] = e;size++;}    //------------------------------------------------测试public static void main(String[] args) {MyArrayList list = new MyArrayList();for(int i=1;i<=10;i++) {list.add(i);}System.out.println(Arrays.toString(list.elements));//System.out.println(list.get(5));//list.set(5, 100);//System.out.println(Arrays.toString(list.elements));//list.remove(9);//System.out.println(Arrays.toString(list.elements));list.add(1, 1000);System.out.println(Arrays.toString(list.elements));}}

稀疏数组

介绍一哈：当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:

1. 记录数组一共有几行几列，有多少个不同的值
2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
   

/** * 应用场景：五子棋 *  * */package dataStructure;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.FileWriter;import java.io.IOException;import java.util.ArrayList;import java.util.List;public class SparseArray {public static void main(String[] args) {//1.首先创建一个二维数组int[][] array1 = new int[11][11];//为这个数组赋值3个，1代表黑子，2代表白子array1[0][4] = 1;array1[1][3] = 1;array1[1][2] = 2;//遍历array1int sum = 0;//用于记录有效数据有多少System.out.println("原始数组为：");for(int[] row : array1) {for(int data : row) {if(data != 0) {sum++;}System.out.print(data+" ");}System.out.println();}//----------------------------------------------------------------------//创建稀疏数组sparseArrayint[][] sparseArray = new int[sum+1][3];sparseArray[0][0] = array1.length;sparseArray[0][1] = array1[0].length;sparseArray[0][2] = sum;//将元素数组中的有效数据存进稀疏数组int count = 0;//用于记录sparseArray数组记录数据到第几行for(int i = 0;i < array1.length;i++) {for(int j=0;j < array1[0].length;j++) {if(array1[i][j] != 0) {count++; sparseArray[count][0] = i;sparseArray[count][1] = j;sparseArray[count][2] = array1[i][j];}}}//输出稀疏数组System.out.println("稀疏数组sparseArray为：");System.out.println("行"+" "+"列"+" "+"值");print(sparseArray);//将稀疏数组保存到磁盘saveSparse(sparseArray);//读取磁盘中的文件，转换为稀疏数组int[][] sparseArray2 = readSparse();if(sparseArray2 != null) {//稀疏数组还原二维数组int[][] array2 = new int[sparseArray2[0][0]][sparseArray2[0][1]];for(int i=1;i <= sparseArray[0][2];i++) {array2[sparseArray2[i][0]][sparseArray[i][1]] = sparseArray2[i][2];}//输出还原后的二维数组System.out.println("还原后的二维数组为：");print(array2);}else {//如果读取的文件没有数据，输出提示语句System.out.println("readSparse()方法返回的结果为：null");}}//----------------------------------------------------------------------public static void print(int[][] array) {for(int[] row : array) {for(int data : row) {System.out.print(data+" ");}System.out.println();}}//----------------------------------------------------------------------//将稀疏数组保存到磁盘中public static void saveSparse(int[][] array) {FileWriter writeFile = null;try {File file = new File("D:\\sparseArray.txt");if(!file.exists()) {file.createNewFile();}writeFile = new FileWriter(file);//开始写入for(int i =0;i < array.length;i++) {//数据前两列加入“，”for(int j = 0;j < 2;j++) {writeFile.write(array[i][j]+",");}//最后一列不加“，”writeFile.write(array[i][2]+"\n");}//把writeFile里的数据全部刷新一次，全部写入文件中writeFile.flush();}catch(Exception e) {e.printStackTrace();}finally {try {//如果writeFile不为空，就将其关闭if(writeFile != null) {writeFile.close();}}catch(IOException e) {e.printStackTrace();}}}//----------------------------------------------------------------------//读取磁盘中的文件，转换为稀疏数组public static int[][] readSparse(){//声明字符输入流FileReader reader = null;//声明字符输入缓冲流BufferedReader rb = null;//声明二维数组int[][] sparseArray1 = null;try {//指定reader的读取路径reader = new FileReader("D:\\sparseArray.txt");//通过BufferedReader包装字符输入流rb = new BufferedReader(reader);//创建集合，用来存放读取的文件的数据List<String> list = new ArrayList<>();String lineStr;//存放一行的数据//逐行读取txt文件里的内容while((lineStr = rb.readLine()) != null) {list.add(lineStr);}int lineNum = list.size();//获取读取的文件有多少行//根据文件行数创建数组sparseArray1 = new int[lineNum][3];int count = 0;//记录输出当前行//循环遍历集合，将集合中的数据放入数组中for(String str : list) {String[] strs = str.split("\\,");sparseArray1[count][0] = Integer.valueOf(strs[0]);sparseArray1[count][1] = Integer.valueOf(strs[1]);sparseArray1[count][2] = Integer.valueOf(strs[2]);count++;}}catch(Exception e) {e.printStackTrace();}finally {//关闭字符输入流try {if(rb != null) {rb.close();}}catch(IOException e) {e.printStackTrace();}}return sparseArray1;}}