数据结构和算法
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)
原因：不用像数组那样为了内存的连续性而移动空间
２．随机查找慢，O(ｎ)
带头链表和不带头链表
带头链表
head指针一直指向一个哨兵结点
哨兵结点不存数据，哨兵的作用：插入第一个结点和插入其他结点，删除第一个结点和删除其他结点都可以统一为相同的代码实现逻辑
哨兵思想
不带头链表
没有哨兵结点
双向链表
循环链表
单向链表的尾结点指向头结点
双向循环链表
数组与链表对比
１．数组简单，链表复杂２.数组连续存贮可借助CPU的缓存机制，访问效率高３．数组要求空间连续，内存易申请失败，切固定大小，不足时需扩容；链表天然支持动态扩容４．链表需要额外的空间来存贮指向指针，数组不需要，且链表的频繁插入删除易造成内存碎片
练习题
LeetCode对应编号：206，141，21，19，876
栈
一种受限制的线性表，只允许一端插入或删除数据
特点：后进先出，先进后出
实现
用数组实现：顺序栈
用链表实现：链式栈
典型应用场景：
函数调用栈
需要练习：１．用栈来计算数学表达式；２、链栈；３、顺序栈
队列
有头有尾
顺序队列：数组实现
链式队列：链表实现
特点：先进先出
队尾插入元素，队头删除元素
所以如果队列用单向链表来实现的话，必须以链表头部作为队头，因为要在头部进行删除，在链表尾部（也是队尾）删除的话，就找不到前面的结点了
典型队列
优先队列
最小堆来实现的
环形队列
阻塞队列
队列为空时取数据会被阻塞，队列满时插入数据会被阻塞；基于阻塞队列可以轻松实现“生产者－消费者模型”
并发队列
循环并发队列
高性能队列 Disruptor
Linux 环形缓存
查找
二分查找
1.循环的执行条件是low<=high，而不是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的缓存不友好２．使用链表需要额外的空间来存贮指针
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表
如何设计工业级的散列表
何为一个工业级的散列表？工业级的散列表应该具有哪些特性？应该有这样几点要求：１、支持快速的查询、插入、删除操作；２、内存占用合理，不能浪费过多的内存空间；３、性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。如何实现这样一个散列表呢？根据前面讲到的知识，我会从这三个方面来考虑设计思路：１、设计一个合适的散列函数；２、定义装载因子阈值，并且设计动态扩容策略；３、选择合适的散列冲突解决方法
哪些底层数据结构是用散列表实现的
Hash算法的应用
1、安全加密
2、唯一标识
3、数据校验
4、散列函数
5、负载均衡
6、数据分片
7、分布式存储
一致性哈希https://www.jianshu.com/p/570dc8913c20
树
二叉树
存储方法
基于指针或引用的二叉链存储法
j基于数组的顺序存储法
树的高度指的是根节点到叶子结点的最长路径（边的个数）
练习
前、中、后、层序遍历
求二叉树的高度
层序遍历
深度优先搜索
二叉查找树
增、删、查
是否是同一棵二叉搜索树
堆
二叉树的前中后序遍历的时间复杂度
从二叉树的遍历图中可以看出，每个结点最多会被访问两次，所以时间复杂度和结点的个数成正比，为Ｏ(n)
树的一些特性
定义：
1.是一个完全二叉树
2.堆的每一个节点的值都必须大于等于（大顶堆）（或小于等于（小顶堆））每个子树中每个节点的值
堆的应用
１.Top K
数据量太大时用Hash算法进行分页，然后采用小顶堆
2.优先队列
合并有序小文件
高性能定时器
３.求中位数
思路很有意思：维护一个大顶堆和一个小顶堆，大顶堆存小数据，小顶堆存大数据，存每次存完如果两个堆中的数据个数不相等就调整到两个堆中的数据个数相同
为什么说堆排序没有快速排序算法快？
堆的特点
1.一般用数组来存储一个堆
2.数组中下标为i的节点，它的左子节点为i*2，右子节点为：i*2+1，父节点的下标为：i/2
3.基础操作
1.插入一个元素
往数组最后加一个元素，然后堆化
2.删除堆顶元素
方法1.直接删除，这样的缺点是容易产生空洞
方法2.将堆顶元素和数据最后一个元素交换，然后堆化
插入一个元素和删除堆顶元素的时间复杂度为O(logn)
分析：一个包含n个节点的完全二叉树的高度不会超过log(n)(以2为底)堆化的过程就是沿着节点的路径进行交换，所以时间复杂度不会超过堆的高度，所以最终的时间复杂度就是O(logn)
3.堆排序
时间复杂度：nlog(n)且非常稳定
分析：建堆的时间复杂度为O(n)，排序为nlog(n)所以总的时间复杂度还是为nlog(n)
空间复杂度：
原地排序，仅交换时需要一个临时变量的空间
过程
1.建堆
最优的方法：时间复杂度为O（n）
方法1.插入一个元素，然后堆化一次，时间复杂度为n*堆化的时间复杂度即：nlog(n)
方法2.先把所有元素按输入顺序放入数组中，然后从下往上调整（堆化），最终建堆的时间复杂度为O（n）(分析过程含有数学推导)
2.排序
排序过程的时间复杂度为nlog(n)
分析：排序过程就是每次从大小为n的堆中拿到堆顶元素，然后将剩余的n-1个元素进行堆化的过程，n个元素，每次堆化log(n)所以总的时间复杂度为nlog(n)
为什么快速排序比堆排序要好？
堆排序比快速排序更加稳定，为什么快速排序还是要比堆排序好呢？
原因
1.堆排序的访问方式没有快速排序好堆排序在堆化的过程中数组下标是跳着访问的（再加上有交换因此不稳定）不像快速排序是局部顺序访问的，所以对CPU的缓存不友好
2.对于同样的数据，堆排序交换的次数要比快速排序多排序过程可看做是消灭逆序对，堆排序的过程中堆化会打乱原来已经有序的数据，所以交换次数会比快速排序多
图
有向图
入度
出度
应用：微博好友之间的关注关系，允许单向关注，可以用有向图来实现
无向图
应用：微信的好友关系
节点叫做顶点
带权图
每条边都有一个权重
应用：QQ好友间的亲密度
存储方式
1.邻接矩阵
缺点：1.稀疏图浪费空间优点：1.基于数组简单高效2.计算方便可以将图的运算转化为矩阵之间的运算3.以空间换时间，节约时间，查询效率高
2.邻接表
优点：1.空间利用率高缺点：1.以时间换空间，所以时间复杂度高
优化
1.如果链表过长，为提高查找效率，可以将邻接表中的链表改为平衡二叉树（如红黑树）或者调表、散列表
应用
1 内存中用临接表2 要持久化存储就用数据库2 超大图 并且涉及大量图计算。用专业的图数据库
深度优先搜索DFS
广度优先搜索BFS
0 条评论
回复 删除
下一页
