乐趣区

关于算法-数据结构:数据结构与算法必知基础知识

jiezi

前言

数据结构与算法是程序员内功体现的重要规范之一，且数据结构也利用在各个方面，业界更有 程序 = 数据结构 + 算法 这个等式存在。各个中间件开发者，架构师他们都在致力的优化中间件、我的项目构造以及算法进步运行效率和升高内存占用，在这里数据结构起到相当重要的作用。此外数据结构也蕴含一些面向对象的思维，故学好把握数据结构对逻辑思维解决形象能力有很大晋升。

为什么学习数据结构与算法？如果你还是学生，那么这门课程是必修的，考研根本也是必考科目。工作在内卷重大的大厂中找工作数据结构与算法也是面试、口试必备的十分重要的考察点。如果工作了数据结构和算法也是内功晋升一个十分重要的体现，对于程序员来说，想要失去称心的后果，数据结构与算法是必备功力！

数据结构

概念

数据结构是计算机存储、组织数据的形式。数据结构是指相互之间存在一种或多种特定关系的数据元素的汇合。通常状况下，精心抉择的数据结构能够带来更高的运行或者存储效率。

简言之，数据结构是一系列的存储构造依照肯定 执行规定 、配合 肯定执行算法 所造成的高效的存储构造。在咱们所熟知的关系数据库、非关系数据库、搜索引擎存储、音讯队列等都是比拟牛的大型数据结构良好的使用。当然这些利用中间件不单单要思考单纯的构造问题。还思考理论 os、网络等其余因素。

而对于数据结构与算法这个专栏。咱们程序员更改把握的首先是在 内存 中运行的 形象的数据结构 。是一个绝对比拟繁多的数据结构类型，比方 线性构造 、 树、图 等等.

相干术语

在数据结构与算法中，数据、数据对象、数据元素、数据项 很多人搞不清其中的关系。通过画一张图来捋一捋，而后上面举个例子给大家分享一下。

用户信息表 users

id name sex
001 bigsai man
002 smallsai man
003 菜虚鲲 woman

users 的 pojo 对象

class users
{ 
     // 略
     int id;
     String name;
     String sex;
}
//list 和 woman 是数据
List<users>list;// 数据对象 list
List<users>woman;// 数据对象 woman
list.add(new users(001,"bigsai","man"));// 增加数据元素 一个 users 由（001，bigsai，man）三个数据项组成 
list.add(new users(002,"smallsai","man"));// 数据元素
list.add(new users(003,"菜虚鲲","woman"));// 数据元素
woman.add(list.get(2));//003,"菜虚鲲","woman" 三个数据项形成的一个数据元素

数据 ：对客观事物的符号示意，指所有能输出到计算机中并被计算机程序解决的符号的汇合总称。上述表中的三条用户信息的记录就是数据(也可能多表多汇合这里只有一个)。这些数据个别都是 用户输出 或者是自定义结构实现。当然，还有一些图像、声音也是数据。

数据元素 ：数据元素是 数据的根本单位 。一个数据元素由若干 数据项 形成！可认为是一个 pojo 对象、或者是数据库的一条记录。比方 菜虚鲲 那条记录就是一个数据元素。

数据项 ：而形成用户字段 / 属性的有id、name、sex 等，这些就是数据项. 数据项是形成数据元素的 最小不可分割字段 。能够看作一个 pojo 对象或者一张表(people) 的一个 属性 / 字段 的值。

数据对象 ：是雷同性质数据元素的汇合。是数据的一个子集。比方下面的users 表、list汇合、woman汇合都是数据对象。独自一张表，一个汇合都能够是一个数据对象。

总的捋一捋，数据范畴最广，所有数据即数据，而数据对象仅仅是有雷同性质的一个汇合，这个汇合是数据的子集，但并不是数据的根本单位，而数据元素才是数据的根本单位。举个例子表 cat 和表 dog 都是数据，而后表 cat 是个数据对象(因为都形容 cat 这种对象)，然而数据的根本单位并不是猫和狗，而是他们的具体的每一条，比方小猫咪 1 号，大猫咪二号，哈士奇 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=15

O(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(n^2)的效率就不敢恭维了。对于大的数据 O(n^2)甚至更高次方的执行成果会很差。

当然如果同样是 n =10000. 那么不同工夫复杂度额算法执行次数、工夫也不同。

具体 n 执行次数
O(1) 10000 1
O(log2n) 10000 14
O(n^1/2) 10000 100
O(n) 10000 10000
O(nlog2 n) 10000 140000
O(n^2) 10000 100000000
O(n^3) 10000 1000000000000

升高算法复杂度有些会靠数据结构的个性和劣势，比方二叉排序树的查找，线段树的动静排序等等，这些数据结构解决某些问题有些十分良好的性能。还有的是靠算法策略解决，比方同样是排序，冒泡排序这种笨而简略的办法就是 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 算法
  • 其余数据结构线段树、后缀数组等等

经典算法

  • 递归算法(求阶乘、斐波那契、汉诺塔问题)
  • 二分查找
  • 分治算法(快排、归并排序、求最近点对等问题)
  • 贪婪算法(应用较多，区间选点问题，区间笼罩问题)
  • 常见动静布局 (LCS(最长公共子序列) LIS(最长回升子序列) 背包问题等等)
  • 回溯算法(经典八皇后问题、全排列问题)
  • 位运算常见问题(参考剑指 offer 和 LeetCode 问题)
  • 疾速幂算法(疾速求幂乘、矩阵疾速幂)
  • kmp 等字符串匹配算法
  • 所有其余数论算法(欧几里得、拓展欧几里得、中国残余定理等等)

置信看完这篇文章，你应该对数据结构与算法有个不错的认知。数据结构与算法有着十分亲密的关联，数据结构是为了实现某种算法，算法是外围目标。学习数据结构与算法之前，能够先参考书本或者博客先理解其性能，再钻研其运行原理，再入手实战 (编写数据结构或者相干题目) 这样档次渐进，想要深刻的学习数据结构与算法光了解是不行的，须要有大量代码实战才可。并且这条路是没有止境的，活到老，学到老，刷到老。

原创公众号：bigsai
文章已收录在 全网都在关注的数据结构与算法学习仓库 欢送 star

咱们下次再见！

退出移动版