算法和数据结构基础知识分享（上）
有哪些常见的数据结构？基本操作是什么？常见的排序算法是如何实现的？各有什么优缺点？本文简要分享算法基础、常见的数据结构以及排序算法。
一 前言
1 为什么要学习算法和数据结构？
解决特定问题。深度优化程序性能的基础。学习一种思想：如何把现实问题转化为计算机语言表示。2 业务开发要掌握到程度？
了解常见数据结构和算法，沟通没有障碍。活学活用：遇到问题时知道要用什么数据结构和算法去优化。二 数据结构基础
1 什么是数据结构？
数据结构是数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据。
数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。
2 物理结构和逻辑结构的区别？
物理结构就像人的血肉和骨骼，看得见，摸得着，实实在在，如数组、链表。
逻辑结构就像人的思想和精神，它们看不见、摸不着，如队列、栈、树、图。
3 线性存储结构和非线性存储结构的区别？
线性：元素之间的关系是一对一的，如栈、队列。非线性：每个元素可能连接0或多个元素，如树、图。三 算法基础
1 什么是算法？
数学：算法是用于解决某一类问题的公式和思想。计算机：一系列程序指令，用于解决特定的运算和逻辑问题。2 如何衡量算法好坏？
时间复杂度：运行时间长短。空间复杂度：占用内存大小。3 怎么计算时间复杂度？
大o表示法（渐进时间复杂度）：把程序的相对执行时间函数t(n)简化为一个数量级，这个数量级可以是n、n^2、logn等。
推导时间复杂度的几个原则：
如果运行时间是常数量级，则用常数1表示。只保留时间函数中的最高阶项。如果最高阶项存在，则省去最高项前面的系数。时间复杂度对比：o(1) > o(logn) > o(n) > o(nlogn) > o(n^2)。
不同时间复杂度算法运行次数对比：
4 怎么计算空间复杂度？
常量空间 o(1)：存储空间大小固定，和输入规模没有直接的关系。
线性空间 o(n)：分配的空间是一个线性的集合，并且集合大小和输入规模n成正比。
二维空间 o(n^2)：分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比。
递归空间 o(logn)：递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合，但是计算机在执行程序时，会专门分配一块内存空间，用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。
5 如何定义算法稳定性？
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
6 有哪些常见算法？
首先要明确：特定算法解决特定问题。
字符串：暴力匹配、bm、kmp、trie等。查找：二分查找、遍历查找等。排序：冒泡排序、快排、计数排序、堆排序等。搜索：tfidf、pagerank等。聚类分析：期望最大化、k-meanings、k-数位等。深度学习：深度信念网络、深度卷积神经网络、生成式对抗等。异常检测：k最近邻、局部异常因子等。......其中，字符串、查找、排序算法是最基础的算法。
四 常见数据结构
1 数组
1）什么是数组？
数据是有限个相同类型的变量所组成的有序集合。数组中的每一个变量被称为元素。
2）数组的基本操作？
读取o(1)、更新o(1)、插入o(n)、删除o(n)、扩容o(n)。
2 链表
1）什么是链表？
链表是一种在物理上非连续、非顺序的数据结构，由若干个节点组成。
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
2）链表的基本操作？
读取o(n)、更新o(1)、插入o(1)、删除o(1)。
3）链表 vs 数组
数组：适合多读、插入删除少的场景。
链表：适用于插入删除多、读少的场景。
3 栈
1）什么是栈？
栈是一种线性逻辑数据结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。
一个比喻，栈是一个一端封闭一端的开放的中空管子，队列是两端开放的中空管子。
2）如何实现栈？
数组实现：
链表实现：
3）栈的基本操作
入栈o(1)、出栈o(1)。
4）栈的应用？
回溯历史，比如方法调用栈。页面面包屑导航。4 队列
1）什么是队列？
一种线性逻辑数据结构，队列的元素只能后进后出。队列的出口端叫做队头，队列的入口端叫做队尾。
2）如何实现队列？
数组实现：
链表实现：
3）队列的基本操作？
入队 o(1)、出队 o(1)。
4）队列的应用
消息队列多线程的等待队列网络爬虫的待爬url队列5 哈希表
1）什么是哈希表？
一种逻辑数据结构，提供了键（key）和值（value）的映射关系。
禾赛与一清达成战略合作布局自动驾驶全生态
BG微络斯移动电源拆解评测：信“芯”十足
洲明科技：做LED视显行业的冲浪儿
基于Lonworks技术和无线通信技术实现数据采集与监控系统的设计
【新专利介绍】基于RTC的供电电路和智能电表
算法和数据结构基础知识分享（上）
稳定币会成为企业的下一个区块链工具吗
NB-IoT智能水表的优势分析
灯具散热问题及可调整式热保护技术深入解读
数据挖掘与机器学习项目特征工程实战
液晶面板的坏点、亮点、暗点
连接器的基本结构
六个助你创建运行更有效率Python应用的窍门
红米note4x、荣耀8、360N5、小米5c这几款千元机的标配，你会选谁？
工业元宇宙：汽车制造业高度自动化|广州华锐互动
俄罗斯将成为通信设备制造商的下一个竞技场
SpaceX或将获准在印度推出“星链“服务
基于三维灰度矩阵的钢板缺陷图像识别算法
诺基亚8要来了，一加3T还能是安卓性价比之王吗？
2018 年的科技趋势，日本点名 AI、AR、VR 将有爆炸性成长
一 前言
1 为什么要学习算法和数据结构？
解决特定问题。深度优化程序性能的基础。学习一种思想：如何把现实问题转化为计算机语言表示。2 业务开发要掌握到程度？
了解常见数据结构和算法，沟通没有障碍。活学活用：遇到问题时知道要用什么数据结构和算法去优化。二 数据结构基础
1 什么是数据结构？
数据结构是数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据。
数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。
2 物理结构和逻辑结构的区别？
物理结构就像人的血肉和骨骼，看得见，摸得着，实实在在，如数组、链表。
逻辑结构就像人的思想和精神，它们看不见、摸不着，如队列、栈、树、图。
3 线性存储结构和非线性存储结构的区别？
线性：元素之间的关系是一对一的，如栈、队列。非线性：每个元素可能连接0或多个元素，如树、图。三 算法基础
1 什么是算法？
数学：算法是用于解决某一类问题的公式和思想。计算机：一系列程序指令，用于解决特定的运算和逻辑问题。2 如何衡量算法好坏？
时间复杂度：运行时间长短。空间复杂度：占用内存大小。3 怎么计算时间复杂度？
大o表示法（渐进时间复杂度）：把程序的相对执行时间函数t(n)简化为一个数量级，这个数量级可以是n、n^2、logn等。
推导时间复杂度的几个原则：
如果运行时间是常数量级，则用常数1表示。只保留时间函数中的最高阶项。如果最高阶项存在，则省去最高项前面的系数。时间复杂度对比：o(1) > o(logn) > o(n) > o(nlogn) > o(n^2)。
不同时间复杂度算法运行次数对比：
4 怎么计算空间复杂度？
常量空间 o(1)：存储空间大小固定，和输入规模没有直接的关系。
线性空间 o(n)：分配的空间是一个线性的集合，并且集合大小和输入规模n成正比。
二维空间 o(n^2)：分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比。
递归空间 o(logn)：递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合，但是计算机在执行程序时，会专门分配一块内存空间，用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。
5 如何定义算法稳定性？
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
6 有哪些常见算法？
首先要明确：特定算法解决特定问题。
字符串：暴力匹配、bm、kmp、trie等。查找：二分查找、遍历查找等。排序：冒泡排序、快排、计数排序、堆排序等。搜索：tfidf、pagerank等。聚类分析：期望最大化、k-meanings、k-数位等。深度学习：深度信念网络、深度卷积神经网络、生成式对抗等。异常检测：k最近邻、局部异常因子等。......其中，字符串、查找、排序算法是最基础的算法。
四 常见数据结构
1 数组
1）什么是数组？
数据是有限个相同类型的变量所组成的有序集合。数组中的每一个变量被称为元素。
2）数组的基本操作？
读取o(1)、更新o(1)、插入o(n)、删除o(n)、扩容o(n)。
2 链表
1）什么是链表？
链表是一种在物理上非连续、非顺序的数据结构，由若干个节点组成。
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
2）链表的基本操作？
读取o(n)、更新o(1)、插入o(1)、删除o(1)。
3）链表 vs 数组
数组：适合多读、插入删除少的场景。
链表：适用于插入删除多、读少的场景。
3 栈
1）什么是栈？
栈是一种线性逻辑数据结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。
一个比喻，栈是一个一端封闭一端的开放的中空管子，队列是两端开放的中空管子。
2）如何实现栈？
数组实现：
链表实现：
3）栈的基本操作
入栈o(1)、出栈o(1)。
4）栈的应用？
回溯历史，比如方法调用栈。页面面包屑导航。4 队列
1）什么是队列？
一种线性逻辑数据结构，队列的元素只能后进后出。队列的出口端叫做队头，队列的入口端叫做队尾。
2）如何实现队列？
数组实现：
链表实现：
3）队列的基本操作？
入队 o(1)、出队 o(1)。
4）队列的应用
消息队列多线程的等待队列网络爬虫的待爬url队列5 哈希表
1）什么是哈希表？
一种逻辑数据结构，提供了键（key）和值（value）的映射关系。
禾赛与一清达成战略合作布局自动驾驶全生态
BG微络斯移动电源拆解评测：信“芯”十足
洲明科技：做LED视显行业的冲浪儿
基于Lonworks技术和无线通信技术实现数据采集与监控系统的设计
【新专利介绍】基于RTC的供电电路和智能电表
算法和数据结构基础知识分享（上）
稳定币会成为企业的下一个区块链工具吗
NB-IoT智能水表的优势分析
灯具散热问题及可调整式热保护技术深入解读
数据挖掘与机器学习项目特征工程实战
液晶面板的坏点、亮点、暗点
连接器的基本结构
六个助你创建运行更有效率Python应用的窍门
红米note4x、荣耀8、360N5、小米5c这几款千元机的标配，你会选谁？
工业元宇宙：汽车制造业高度自动化|广州华锐互动
俄罗斯将成为通信设备制造商的下一个竞技场
SpaceX或将获准在印度推出“星链“服务
基于三维灰度矩阵的钢板缺陷图像识别算法
诺基亚8要来了，一加3T还能是安卓性价比之王吗？
2018 年的科技趋势，日本点名 AI、AR、VR 将有爆炸性成长