首页  思维导图  详情

数据结构与算法

2020-05-11 14:53:43   3  举报





AI智能生成

数据结构与算法

算法

数据结构

作者其他创作

大纲/内容

基础

复杂度

时间复杂度

分析时间复杂度方法

1.只关注循环执行次数最多的一段代码

2.加法法则：总复杂度等于量级最大的那段代码的复杂度

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂

常见复杂度实例

空间复杂度

常见的时间复杂度就是O（1）、O(n)、O(n2)

复杂度分析方面

最好情况时间复杂度

最坏情况时间复杂度

平均情况时间复杂度

均摊时间复杂度

排序

执行效率

最好情况，最坏情况，平均情况时间复杂度

时间复杂度的系数、常数、低阶

比较次数和交换（或移动）次数

内存消耗

稳定性

有序度

逆序度

归并排序

原理

如果排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。

性能分析

稳定排序

这样就保证了值相同的元素，合并前后的先后顺序不变。

时间复杂度

空间复杂度

不是原地排序，O(n)

快速排序

如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot(分区点)

我们遍历p到r之间的数据,将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据分成三部分，前面p到q-1之间都是小于pivot,中间pivot,后面q+1到r之间是大于pivot的。

归并排序中有一个merge()合并函数，我们这里有一个partition（）分区函数，partition()分区函数实际上我们前面已经讲过了，就是随机一个元素作为pivot(一般情况下，可以选择p到r区间的最后一个元素)，然后A[p...r]分区，函数返回pivot的下标。

处理分区

partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i

这里的处理类似选择排序，我们通过游标i把A[p...r-1]分成两部分。A[p...i-1]的元素都是小于pivot的，我们暂且叫它“已处理区间”，A[i...r-1]是“未处理区间”。我们每次都从未处理的区间A[i...r-1]中取一个元素a[j],与pivot对比，如果小于pivot，则将其加人到已处理区间的尾部，也就是A[i]的位置。

在数组某个位置插入元素，需要搬移数据，非常耗时，当时我们将了一种处理技巧，就是交换，在O(1)的时间复杂度完成插入操作。这里我们也借助这个思想，只需要将A[i]与A[j]交换，就可以将O(1)时间复杂度内将A[j]放到下标i的位置。

根据分治，递归思想，我们可以用递归排序下标从p到q-1之间的数据和q+1到r之间数据，直到区间缩小为1.

递推公式

quick_sort(p...r) = quick_sort(p..q-1)+quick_sort(q+1,r)

归并和快速排序区别

可以发现，归并排序处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它处理过程是由上到下，先分区，然后再处理子问题，归并排序虽然稳定，时间复杂度为O(nlogn)的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存问题。

线性排序

桶排序

如果要排序的数据有n个，我们把它们均匀的划分到m个桶内，每个桶内就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度O（k*logk）。m个桶排序的时间复杂度就是O(m*k*logk),因为k=n/m,所以整个桶排序时间复杂度就是O(n*log(n/m))。当桶的个数m接近数据个数n时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。

数据在各个桶之间分布比较均匀

计数排序

计数排序是桶排序的特殊情况

计数排序只能用在数据不大的场景中，如果数据范围k比要排序的数据n大很多，就不适用计数排序了。而且，计数排序只能给非负整数排序。

基数排序

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。

区别

桶排序和计数排序排序思想相似，都是针对范围不大的数据，将数据划分成不同的桶来实现排序。基数排序要求数据可以划分高低位，位之间有递进关系。如果a数据高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位数据范围不能太大，就可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)

排序优化

对于小规模数据进行排序，可以选择O(n2)的算法；如果大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效，所以为了兼顾任意规模的数据排序，一般都会首选时间复杂度O(nlogn)。

优化快排

数据原来就是有序或者接近有序的，每次分区点都选择最后一个数据，那么快速排序算法就会变得糟糕

选择合理的分区点

被分区点分开的两个分区中，数据数量差不多

三数取中法

随机法

快排是递归实现

递归要警惕堆栈溢出

查找

二分查找

二分查找针对的是一个有序数据集合，查找思想有点类似分治思想，每次都通过跟分区的中间元素对比，将待查找区间缩小为之前一半，直到找到查找的元素，或者区间缩小0

最简单情况

有序数组中不存在重复元素

容易出错的地方

循环退出条件

low<=high 而不是low<high

mid取值

mid=(low+high)/2容易溢出

low和high更新

low=mid+1,high=mid-1。注意这里+1和-1，如果直接写成low=mid或者high=mid，就可以发生死循环

比如，当high=3,low=3时，如果a[3]不等于value，就会导致一直循环不退出。

变形

查找第一个值等于给定值得元素

查找最后一个值等于给定值得元素

查找第一个大于等于给定值得元素

查找最后一个小于等于给定值的元素

二分查找更适合用在“近似”的查找问题，在这类问题上，二分查找的优势更加明显。

跳表

链表加多级索引的结构

实现？

散列表

散列表用数组支持按照下标随机访问数据的特性，所以散列表其实数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

装载因子=填入表中元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

散列函数设计基本要求

散列函数计算得到散列值是一个非负整数

如果key1 = key2,那hash(key1) == hash(key2)

如果key1 != key2 ,那hash(key1) != hash(key2)

散列冲突

开放寻址法

线性探测

插入

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

删除

在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在的这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。

删除元素标记deleted

二次探测

所谓二次探测跟线性探测很像，线性探测每次探测步长是1，那它探测的下标序列就是hash(key)+0.hash(key)+1,hash(key)+2 ...... 而第二次探测步长就

双重散列

所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

链表法

我们只需要通过散列函数计算对应的散列槽位，将其插入到对应链表中即可，所以插入时间复杂度是O(1)。

当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。

实际上这两个操作的时间复杂度跟链表的长度k成正比，也就是O(k)

工业级水平的散列表

在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。

如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。

装载因子过大

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突概率越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找过程也会因此变得很慢。

子主题

哈希算法

定义

将任意长度二进制值串映射为固定长度的二进制值串

特点

从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）

对输入数据非常敏感，哪怕原始数据只修改一个bit,最后得到的哈希值也大不相同。

散列冲突的概率要很小，对应不同的原始数据，哈希值相同概率非常小；

哈希算法的执行效率尽量高效，针对较长的文本，也能快速地计算出哈希值。

应用

安全加密

算法

MD5（MD5消息摘要算法）

SHA(安全散列算法)

DES(数据加密标准)

AES(高级加密标准)

唯一标识

数据校验

散列函数

负载均衡

数据分片

分布式存储

图

非线性数据结构

图中的元素我们就叫作顶点（vertex）。从我画的图中可以看出来，图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边（edge）。

度

跟顶点相连的边的条数

无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图，我们把度分为入度和出度。带权图，每条边都有一个权重（weight）

邻接矩阵

存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。

邻接表存储

广度优先

广度优先搜索（Breadth-First-Search）,我们平常都把简称为BFS,直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近，然后是次近，依次往外搜索。

时间复杂度

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。

空间复杂度

广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

深度优先

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

时间复杂度

每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。

空间复杂度

深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。解答开篇

树

树、二叉树

树

节点的高度

节点到叶子节点的最长路径（边数）

从下往上度量

树的高度

根节点的高度

节点的层数

节点的深度+1

节点的深度

根节点到这个节点所经历边的个数

从上往下度量

二叉树

满二叉树

编号2的二叉树，叶子节点全部在最底层，除了叶子节点之外，每个节点都有左右两个节点，这种二叉树叫做满二叉树

完全二叉树

编号3的二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树完全二叉树

如何存储一棵二叉树

一种是基于指针或者引用二叉链式存储法

一种基于数组顺序查找

堆是一棵完全二叉树

二叉树遍历

二叉查找树

平衡二叉查找树、红黑树

二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2n的情况，从而导致各个操作的效率下降。极端的情况下，二叉树退化成链表，时间复杂会退化到O(n)。

解决退化问题，我们设计一种平衡二叉树

简介

二叉树中任意一个节点的左右子树的高度相差不能大于1

示例

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。

AVL树,

红黑树，不是严格意义平衡二叉查找树

红黑树

满足要求

根节点是黑色

每个叶子节点都是黑色的空节点（NIL）,也就是说，叶子节点不存储数据。

任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色隔开的的。

每个节点，从该节点到达其可达的叶子节点的所有路径，都包含相同数目的黑色节点。

红黑树的插入、删除操作就会破坏红黑树的定义，具体来说就会破坏红黑树的平衡

插入操作平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。

两种特殊情况

如果插入节点的父节点是黑色的，我们什么都不用做，它仍然满足红黑树定义。

如果插入节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以。

删除操作平衡调整

第一步骤

针对删除节点初步调整。初步调整只是保证整颗树红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同的黑色节点。

第二步骤

针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

平衡二叉树

平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；

规则

非叶子节点只能允许最多两个子节点存在

每一个非叶子节点数据分布规则为左边的子节点小于当前节点的值，右边的子节点大于当前节点的值（这里值是基于自己的算法规则而定的，比如hash值）

二叉树中任意一个节点的左右子树的高度相差不能大于1(保证查询难度)

没有值相等重复的节点

B树

B树与B-树是同一种树

简介

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构

规则

排序方式

所有节点关键字是递增次序排序，并遵循左小右大原则

子节点数

非叶节点的子节点数>1,且<=M,且M>=2,空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路，当M=2则是2叉树）

关键字数

非根节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);

所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都null

流程

直接用实际字母的大小来排列C>B>A

查询

查找E

流程

获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；

拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

插入

简介

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

流程

先插入 3、8、31、11

再插入23、29

再插入50、28

删除

简介

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

流程

节点合并规则：当前是要组成一个5路查找，那么此时m=5.关键字数必须大于等于ceil(5/2)(这里关键字数<2就要进行节点合并)

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

满足节点本身比左节点

关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

特点

B树相对于平衡二叉树的不同是，每个节点包含关键字增多，特别的是B树应用到数据库的时候，数据库充分利用磁盘块原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把结点大小限制和充分使用在磁盘块大小范围；把树的节点关键字增多后树的层级比原来二叉树少了，减少数据查找的次数和复杂度

B+树

维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。

非叶子节点的子节点数=关键字数（来源百度百科）

规则

B+树包含2种类型的结点：内部节点（索引节点）和叶子节点。根节点本身即可是内部节点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

内部结点中key都按照从小到大的顺序排序，对于内部结点中一个key，左树中所有key都小于它，右子树中key都大于等于它，叶子节点中的记录也按照key的大小排列。

每个叶子结点都存有相邻叶子结点指针，叶子结点本身关键字大小自小而大顺序链接

插入

规则

若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。

针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录，插入后，若当前结点key的个数小于等于m-1,则插入结束。否则将这个叶子结点分裂成左右成两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。

针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

删除

1）删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束,否则执行第2步。

2）若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。

3）若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。

4）若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第5步

5）若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步

6）当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。

下面是一颗5阶B树的删除过程，5阶B数的结点最少2个key，最多4个key。

特点

B+树层级更少：相较于B树B+树每个非叶子节点存储的关键字数更多，树层级更少所以查询数据更快

B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

递归树

堆

完全二叉树

除了最后一层，其他层的节点个数都是满的，最后一层节点都靠左排列。

堆中每个每个节点的值必须大于等于（或者小于等于）其子树种每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（小于等于）其左右节点的值。这两种表述是等价。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

应用

优先级队列

topk

中位数

字符串

BF算法

BF算法中BF是BruteForce的缩写，中文叫做暴力匹配算法，也叫做朴素匹配算法。

它们分为主串和模式串

比如。字符串A中查找字符串B,那么字符串A就是主串，字符串B就是模式串。

主串长度记作n,模式串长度m,n>m

RK算法

子主题

BM算法

子主题

结构

线性表

数组

简介

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

连续的内存空间和相同类型的数据

特性：“随机访问”。但有利有弊，这两个限制也让数组很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要要做大量的数据搬移工作。

数组如何实现根据下标随机访问数组元素

base_address=1000 内存块的首地址

计算每个内存单元分配一个地址

a[i]_address = base_address + i*data_type_size

data_type_size 表示数组中每个元素的大小

纠正

链表适合插入、删除，时间复杂度O(1)

数组适合查找，查找时间复杂度O(1)

数组适合查找操作，但是查找时间复杂度并不为O(1)。即便排序好的数组，使用二分查找，时间复杂度O(logn)。所以，正确表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度O(1)。

低效的"插入"和"删除"

插入操作

如果数组中数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移k之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当做一个存储数据的集合。在这种情况下，如果要将某个数组插入到第k个位置，为了避免大规模数据搬移，我们还有一个简单的办法就是，直接将第k位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置。

a[10]中存储5个元素：a,b,c ,d,e

x插入第三个位置，结果：a,b,x,d,e,c

删除操作

跟插入类似，如果删除数组末尾数据，则最好的情况复杂时间复杂度O(1);如果删除开头的数据，则最坏情况时间复杂度O(n);平均情况时间复杂时间复杂度也O(n)。

数组a[10]中存储8个元素：a,b,c,d,e,f,g,h现在，我们要依次删除a,b,c三个元素。

为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

jvm标记清除算法类似

队列

链表

链表适合插入、删除，时间复杂度O(1)

链表想要随机访问第k个元素，就没有数组那么高效。

技巧