原始公众号： bigsai
文章收录在全网关注的数据结构和算法学习仓库，欢迎star
前言数据结构和算法是程序员内功体现的重要标准之一，而且数据结构也应用于各个方面，行业中存在程序=数据结构+算法的等式。 每个中间件开发人员和架构师都在努力优化中间件、项目结构和算法，提高执行效率和减少内存使用，其中数据结构起着相当重要的作用。 而且，由于数据结构还包含面向对象的思想，学好数据结构可以大大提高逻辑思维处理的抽象能力。
为什么要学习数据结构和算法？ 如果你还是学生的话，这个课程是必修的，应试学习也基本上是必修课。 在内卷严重的大厂找工作数据结构和算法也是面试、笔试必备的一个非常重要的考察点。 把数据结构和算法做好工作也是内功提升的一个非常重要的体现，数据结构和算法是程序员获得满意结果的必由之功
数据结构
概念数据结构是计算机存储和组织数据的方法。 数据结构是相互具有一个或多个特定关系的数据元素的集合。 通常，精心选择的数据结构会带来更高的操作效率或存储效率。
简单来说，数据结构是一系列存储结构按照一定执行规则、与一定的执行算法相匹配而形成的高效存储结构。 众所周知的关系数据库、非关系数据库、搜索引擎存储和消息队列等都很好地利用了相对牛的大数据结构。 当然，这些APP应用中间件必须只考虑简单的结构问题。 也考虑了实际操作系统、网络等其他因素。
关于数据结构和算法这一专栏。 我们程序员变更后掌握的首先是内存中运行的抽象数据结构。 线性结构、树、图等比较单一的数据结构类型。
相关术语在数据结构和算法中，数据、数据对象、数据元素、数据项很多人无法理解其关系。 通过画画来捋，接下来举例和大家分享。
用户信息表用户
idname sex 001 bigsaiman 002 smallsaiman 003烹饪大鲵womanusers的pojo对象
class users{ //稍int id； 字符串名称； 字符串sex； }//list和woman是数据监听器列表； //数据对象listListuserswoman； //数据对象woman list.add (新用户(001，' bigsai '，' man ' ) )//用于添加数据元素的一个users有三个数据： (001，bigsai，man ) //数据元素list.add(newusers(003，'料理虚鲲'，' woman ' ) )//数据元素Woman.add(list.get(2) )； //003、“菜虚馆”、“woman”三个数据项组成的一个数据元素数据“客观事物的符号表示”可以输入计算机，由计算机程序处理上表中的3个用户信息的记录就是数据。 (多个表格聚集在一起，这里可能只有一个。 这些数据通常由用户输入或以自定义结构创建。 当然，一些图像，声音也是数据。
数据元素:数据元素为数据的基本单位。 一个数据元素由几个数据项组成！ 它可以是pojo对象或数据库的记录。 例如，烹饪鲱鱼的记录是一个数据元素。
数据项:并且，构成用户字段/属性的有id、name、sex等，这些是数据项。 数据项是构成数据要素的最小不可分割字段。 可以将其视为pojo对象或表格属性/字段的值。
数据对象:是相同性质的数据元素的集合。 是数据的子集。 例如，上面的users表、list集合和woman集合都是数据对象。 一个表，一个集合可以是一个数据对象。
的综合操作，数据范围最广，所有数据都是数据，但数据对象只是具有相同性质的一个集合。 该集合是数据的子集，但不是数据的基本单位，数据元素才是数据的基本单位。 举个例子，表cat和表dog都是数据。 而且，表cat是数据对象。 (因为它描述了一个对象cat )但是数据的基本单位不是猫和狗，而是他们的具体各项。 例如，1号猫、2号猫、1号西伯利亚雪橇犬、2号藏獒等是数据的基本单位。
也有数据类型。 抽象数据类型也将在下面说明。
数据类型
原子类型：该值不能重新划分的类型。 例如int、char、double、float等。
结构类型：值还可以分为几个成分的数据类型。 例如结构体结构的各种结构等。
抽象数据类型(ADT):抽象数据类型(ADT )是一种实现包含存储数据元素的存储结构和基本操作的算法。 不考虑实现的详细情况，只研究其结构就可以使用。 例如，为了使用List、Map、Set等，只要理解其api和性质功能即可。 具体的实现可能是不同的方案。 例如，List的实现有数组和链表
不同选择。 三要素逻辑结构：数据元素之间的逻辑关系。逻辑结构分为线性结构和非线性结构。线性结构就是顺序表、链表之类。而非线性就是集合、树、图这些结构。
存储结构：数据结构在计算机中的表示(又称映像，也称物理结构)，存储结构主要分为顺序存储、链式存储、索引存储和散列(尊敬的路人)存储，这几种存储通过下面这张图简单了解一下(仅仅为理解不考虑更多)：
数据的运算：施加在数据上的运算包括运算的定义和实现,运算的定义基于逻辑结构，运算的实现基于存储结构。
在这里容易混淆的是逻辑结构与存储结构的概念。对于逻辑结构，不难看得出逻辑二字，逻辑关系也就是两者存在数据上的关系而不考虑物理地址的关系，比如线性结构和非线性结构，它描述的是一组数据中联系的方式和形式，他针对的是数据。看中的是数据结构的功能，比如线性表就是前后有序的，我需要一个有序的集合就可以使用线性表。
而存储结构就是跟物理地址挂钩的。因为同样逻辑结构采用不同存储结构实现适用场景和性能可能不同。比如同样是线性表,可能有多种存储结构的实现方式。比如顺序表和链表(Arraylist,Linkedlist)它们的存储结构就不同，一个是顺序存储(数组)实现，一个是链式存储(链表)实现。它关注的是计算机运行物理地址的关系。但通常同一类存储结构实现的一些数据结构有一些类似的共同点和缺点(线性易查难插、链式易插难查等等)。
算法分析上面讲了数据结构相关概念，下面对算法分析的一些概念进行描述。
算法的五个重要特征：有穷性、确定性、可行性、输入、输出。这些从字面意思即可理解，其中有穷性强调算法要有结束的时候不能无限循环；而确定性是每条指令有它意义，相同的输入得到相同的输出；可行性是指算法每个步骤经过若干次执行可以实现；输入是0个或多个输入(可0);输出是1个或多个输出(一定要有输出)。
而一个好的算法，通常更要着重考虑的是效率和空间资源占用(时间复杂度和空间复杂度)，通常复杂度更多描述的是一个量级程度而很少用具体数字描述。
空间复杂度概念：是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))
空间复杂度其实在算法的衡量占比是比较低的(我们经常使用牺牲空间换时间的数据结构和算法)，但是不能忽视空间复杂度中重要性。无论在刷题还是实际项目生产内存都是一个极大额指标。对于Java而言更是如此。本身内存就大，如果采用的存储逻辑不太好会占用更多的系统资源，对服务造成压力。
而算法很多情况都是牺牲空间换取时间(效率)。就比如我们熟知的字符串匹配String.contains()方法，我们都知道他是暴力破解，时间复杂度为O(n^2),不需要借助额外内存。而KMP算法在效率和速度上都原生暴力方法，但是KMP要借助其他数组(next[])进行标记储存运算。就用到了空间开销。再比如归并排序也会借助新数组在递归分冶的适合进行逐级计算，提高效率，但增加点影响不大的内存开销。
当然，算法的空间花销最大不能超过jvm设置的最大值，一般为2G.(2147483645)如果开二维数组多种多维数据不要开的太大，可能会导致heap OutOfMemoryError。
时间复杂度概念：计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
时间复杂度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)
常见时间复杂度：对于时间复杂度，很多人的概念是比较模糊的。下面举例子说明一些时间复杂度。
O(1): 常数函数
a=15O(logn): 对数函数
for(int i=1;i<n;i*=2)分析：假设执行t次使得i=n;有2^t=n; t=log2~n,为log级别时间复杂度为O(logn)。还有典型的二分查找，拓展鲤鱼棒球，快速幂等算法均为O(logn)。属于高效率算法。
O(n): 线性函数
for (int i=0;i<n;i++)比较常见，能够良好解决大部分问题。O(nlogn):
for (int i=1;i<n;i++)for (int j=1;j<i;j*=2)常见的排序算法很多正常情况都是nlogn，比如快排、归并排序。这种算法效率大部分也还不错。
O(n^2)
for(int i=0;i<n;i++)for(int j=0;j<i;j++)其实O(n2)的效率就不敢恭维了。对于大的数据O(n2)甚至更高次方的执行效果会很差。
当然如果同样是n=10000.那么不同时间复杂度额算法执行次数、时间也不同。
具体n执行次数O(1)100001O(log2n)1000014O( n^1/2)10000100O(n)1000010000O(nlog2 n)10000140000O(n^2)10000100000000O(n^3)100001000000000000降低算法复杂度有些会靠数据结构的特性和优势，比如二叉排序树的查找，线段树的动态排序等等，这些数据结构解决某些问题有些非常良好的性能。还有的是靠算法策略解决，比如同样是排序，冒泡排序这种笨而简单的方法就是O(n2),但快排、归并等聪明方法就能O(nlogn)。要想变得更快，那就得掌握更高级的数据结构和更精巧的算法。
时间复杂度计算
时间复杂度计算一般步骤：1、找到执行次数最多的语句; 2、计算语句执行的数量级 ; 3、用O表示结果。并且有两个规则：
加法规则： 同一程序下如果多个并列关系的执行语句那么取最大的那个,eg:
T(n)=O(m)+O(n)=max(O(m),O(n)); T(n)=O(n)+O(nlogn)=max(O(n),O(nlogn))=O(nlogn);乘法规则：循环结构，时间复杂度按乘法进行计算,eg：
T(n)=O(m)*O(n)=O(mn)T(n)=O(m)*O(m)=O(m^2)(两层for循环)当然很多算法的时间复杂度还跟输入的数据有关，分为还会有最优时间复杂度(可能执行次数最少时)，最坏时间复杂度(执行次数最少时)，平均时间复杂度，这在排序算法中已经具体分析，但我们通常使用平均时间复杂度来衡量一个算法的好坏。
数据结构与算法学习捋过数据结构与算法基本概念的介绍，在学习数据结构与算法方面，个人把经典的数据结构与算法学习过程步骤写在下面，希望能给大家一个参考：
数据结构单链表(带头结点、不带头结点)设计与实现(增删改查)，双链表设计与实现
栈设计与实现(数组和链表)，队列设计与实现(数组和链表)
二叉树概念学习，二叉树前序、中序、后序遍历递归、非递归实现 ，层序遍历
二叉排序树设计与实现(插入删除)
堆(优先队列、堆排序)
AVL(平衡)树设计与实现(四种自旋方式理解实现)
伸展树、红黑树原理概念理解
B、B+原理概念理解
哈夫曼树原理概念理解(贪心策略)
尊敬的路人(散列表)原理概念理解(几种解决尊敬的路人冲突方式)
并查集/不相交集合(优化和路径压缩)
图论拓扑排序
图论dfs深度优先遍历、bfs广度优先遍历
最短路径Dijkstra算法、Floyd算法、spfa算法
最小生成树prim算法、kruskal算法
其他数据结构线段树、后缀数组等等
经典算法 递归算法(求阶乘、斐波那契、hldby问题)二分查找分治算法(快排、归并排序、求最近点对等问题)贪心算法(使用较多，区间选点问题，区间覆盖问题)常见动态规划(LCS(最长公共子序列) LIS(最长上升子序列)背包问题等等)回溯算法(经典八皇后问题、全排列问题)位运算常见问题(参考剑指offer和LeetCode问题)快速幂算法(快速求幂乘、矩阵快速幂)kmp等字符串匹配算法一切其他数论算法(鲤鱼棒球、拓展鲤鱼棒球、中国剩余定理等等)相信看完这篇文章，你应该对数据结构与算法有个不错的认知。数据结构与算法有着非常密切的关联，数据结构是为了实现某种算法，算法是核心目的。学习数据结构与算法之前，可以先参考书本或者博客先了解其功能，再研究其运行原理，再动手实战(编写数据结构或者相关题目)这样层次渐进，想要深入的学习数据结构与算法光理解是不行的，需要有大量代码实战才可。并且这条路是没有止境的，活到老，学到老，刷到老。
愿大家2021一起加油，2021我会把专栏数据结构与算法系列文章进行优化输出！这是第一篇，敬请期待！
原创不易，bigsai请csdn的朋友们帮两件事帮忙一下:
点赞、在看、分享支持一下， 您的肯定是我创作的源源动力。
微信搜索「bigsai」，2021我需要你的支持！
咱们下次再见！