首页  思维导图  详情

数据结构和算法

2020-11-04 14:23:21   0  举报





AI智能生成

数据结构和算法

数据结构

作者其他创作

大纲/内容

递归

可以用递归解决的问
题应该满足的条件

1.一个问题的解可以分解为几个子问题

2.这个问题和分解后的子问题，除了数据规模不同，求解思路完全一样

3.存在递归终止条件

注意事项

递归代码要警惕堆栈溢出

最大允许递归的深度和当前线程剩余的栈空间大小有关

递归代码要警惕重复计算

函数调用耗时多

空间复杂度高

所有的递归都可以用迭代循环实现

因为递归本身就是借助栈来实现的

递归代码若规模较大，层次较深，几乎无法用IDE来进行单步调试

正确的调试方法：
1.打日志，记录递归值
2.利用条件断点

排序

冒泡排序

插入排序

选择排序

归并排序

快速排序

防止栈溢出的方法：
第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。
第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制

计数排序

１、计数排序只能用在数据范围不大的场景中，如果数据范围k比要
排序的数据n大很多，就不适合用计数排序了。
２、计数排序只能给非负整数排序，如果要排序的数据是其他类型的，
要将其在不改变相对大小的情况下，转化为非负整数

基数排序

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

桶排序

桶排序适合在外部排序中使用，所谓的外部排序就是数据存储在外部磁
盘中，数据量比较大，内存有限，无法将数据全部加载到内存中

总结

桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分成不同的桶来实现
排序。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，
高位相同的再比较低位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数
排序来完成每一个位的排序工作。

在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长。
所以，对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法

linux系统中最底层的api:glibc中qsort()的实现

１、数据规模小时用归并排序

２、数据规模大时切换到快速排序

３、快速排序采用了“三数取中法"来选主元

４、当元素小于４个时，快速排序退化为插入排序

５、插入排序中用哨兵来避免不必要的比较

定理

定理１：任意Ｎ个不同元素组成的序列平均有Ｎ(N-1)/4个逆序对

定理２：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ｏ(n^2)

时间\空间复杂度

数据规模很大时的一种增长趋势
所以一般会忽略系数、常数、低阶

数组

链表

常用的链表

单向链表

头结点

第一个结点

尾结点

最后一个结点

指向null

特性

１．插入、删除快，时间复杂度Ｏ(1)

原因：不用像数组那样为了内存的连续性
而移动空间

删除的时间复杂度是Ｏ(1),但是删除给定值的复杂度为Ｏ(n)，因为需要遍历到给定值

２．随机查找慢，O(ｎ)

带头链表和不带头链表

带头链表

head指针一直指向一个哨兵结点

哨兵结点不存数据，哨兵的作用：插入第一个结点和插入其他结点，删除第一个结点和
删除其他结点都可以统一为相同的代码实现逻辑

哨兵思想

不带头链表

没有哨兵结点

双向链表

循环链表

单向链表的尾结点指向头结点

双向循环链表

数组与链表对比

１．数组简单，链表复杂
２.数组连续存贮可借助CPU的缓存机制，访问效率高
３．数组要求空间连续，内存易申请失败，切固定大小，不足时需扩容；链表天然支持动态扩容
４．链表需要额外的空间来存贮指向指针，数组不需要，且链表的频繁插入删除易造成内存碎片

练习题

LeetCode对应编号：206，141，21，19，876

栈

一种受限制的线性表，只允许一端插入或删除数据

特点：后进先出，先进后出

实现

用数组实现：顺序栈

用链表实现：链式栈

典型应用场景：

函数调用栈

leetcode上关于栈的题目:20,155,232,844,224,682,496.

需要练习：１．用栈来计算数学表达式；２、链栈；３、顺序栈

队列

有头有尾

实现

顺序队列：数组实现

链式队列：链表实现

特点：先进先出

队尾插入元素，队头删除元素

所以如果队列用单向链表来实现的话，必须以链表头部作为队头，
因为要在头部进行删除，在链表尾部（也是队尾）删除的话，
就找不到前面的结点了

典型队列

优先队列

最小堆来实现的

环形队列

循环队列实现时：一般空出一个位置不放元素，原因在于判断队列的空和满，如果不空出一个元素时
队列空和满都指向同一个位置（当然也可以引入队列大小这个判据来区分队列的空和满）根本原因在
于：队列的状态是根据头和尾之间的差值来进行判断的，假如一个队列中有n=６个位置,头和尾之间
的差值就有０到５（ｎ-1）共６（ｎ）种情况，如果队列满的话就一共有7(n+1)种情况
（０个元素，１个元素...６个元素共７种）,所以一般会空出一个位置，来区分空满的情况

阻塞队列

队列为空时取数据会被阻塞，队列满时插入数据会被阻塞；基于阻塞队列可以轻松实现“生产者－消费者模型”

并发队列

循环并发队列

高性能队列 Disruptor

Linux 环形缓存

查找

二分查找

注意事项

1.循环的执行条件是low<=high，而不是low<high

2.mid=low+(high-low)/2,追求极致的写法为：low+((high-low)>>1)而不是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，就会导致一直循
环不退出。

适用场景

１．二分查找依赖的数组，必须是顺序结构，链表不行

２、二分查找的前提必须是有序的

３、二分查找不适用于数据量太小的场景，数据量过小时直接遍历就好了，
当然如果“比较操作”的成本过高，二分查找可以减少遍历次数，还是会比
遍历要好

４、二分查找不适用与数据量过大的场景，因为二分查找的基础是数组，
数组要求存储空间是连续的，在空间足够但是不连续的情况下还是会出现
内存分配失败的情况

散列表（Hash Table）

特性：由数组演化而来，利用的是数组根据下标随机查找的特性，是数组的扩展，没有数组就没有散列表

装载因子

散列表的装载因子=填入表中的元素个数/散列表的长度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降

Hash函数设计
的三点要求

1. 散列函数计算得到的散列值是一个非负整数；
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
第三点很难做到，所以产生了散列冲突问题

解决散列冲突的两类方法

１．开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，
我们就重新探测一个空闲位置，将其插入。

１．线性探测

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

２．二次探测

所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测
的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探
测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是
hash(key)+0，hash(key)+12，hash(key)+22……

３．多重散列

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

注意点

1.删除：
删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。这是为什么呢？
还记得我们刚讲的查找操作吗？在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们
就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查
找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？
我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，
并不是停下来，而是继续往下探测。

优点

１、存在连续的数组中，可以有效利用CPU的缓存加快查找速度
２、序列化起来相比链表发简单

适用场景

适用于数据量小，装载因子小的场景

缺点

１．删除数据比较麻烦
２．冲突的代价更大

２、链表法

当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

优点

１．不需要事先申请内存，空间利用率更高
２、对装载因子的容忍度高（散列函数设计的合理，装载因子再大也无所谓）
３、我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲
突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是
O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

缺点

１．在内存中零散分布，对cpu的缓存不友好
２．使用链表需要额外的空间来存贮指针

适用场景

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更
加灵活，支持更多的优化策略，比如用红黑树代替链表

如何设计工业级的散列表

何为一个工业级的散列表？工业级的散列表应该具有哪些特性？
应该有这样几点要求：
１、支持快速的查询、插入、删除操作；
２、内存占用合理，不能浪费过多的内存空间；
３、性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。
如何实现这样一个散列表呢？根据前面讲到的知识，我会从这三个方面来考虑设计思路：
１、设计一个合适的散列函数；
２、定义装载因子阈值，并且设计动态扩容策略；
３、选择合适的散列冲突解决方法

哪些底层数据结构是用散列表实现的

比如Redis中的hash,set,hset,都是散列表实现，他们的动态
扩容策略是同时维护两个散列表，然后一点点搬移数据

Hash算法的应用

1、安全加密

2、唯一标识

3、数据校验

4、散列函数

5、负载均衡

6、数据分片

7、分布式存储

一致性哈希
https://www.jianshu.com/p/570dc8913c20

树