数据结构和算法
2019-12-05 11:30:39 60 举报AI智能生成
登录查看完整内容
数据结构和算法
作者其他创作
大纲/内容
数据结构和算法
为什么要学习数据结构和算法
如何高效学习数据结构和算法
概念：广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法
学习基础：高中数学、基本编辑技巧
学习重点：复杂度分析
学习技巧：
1. 边学边练，适度刷题
2. 多问、多思考、多互动
3. 打怪升级学习法
4. 知识需要沉淀，不要想试图一下子掌握所有
20个常用、基础的数据结构和算法
数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
书籍推荐
复杂度分析
事后统计法的局限性
1. 测试结果非常依赖测试环境
2. 测试结果受数据规模的影响很大
大 O 复杂度表示法
1.公式：T(n) = O(f(n))
2.代码的执行时间 T(n) 与每行代码的执行次数 n 成正比
3.代码执行时间随数据规模增长的变化趋势，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
时间复杂度分析
技巧
1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
知识点
最好情况时间复杂度
最坏情况时间复杂度
平均情况时间复杂度(又称加权平均时间复杂度或者期望时间复杂度)
均摊时间复杂度(一种特殊的平均时间复杂度)
时间复杂度量级
多项式
1. 常量O(1)
2. 对数阶O(logn)、O(nlogn)
3. 两个数据规模 O(m+n)、O(m*n)
非多项式
1. O(2n)
2. O(n!)
空间复杂度
空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
常见的空间复杂度就是 O(1)、O(n)、O(n2)
数组
定义
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
特点
1.线性表（Linear List）
①线性表：数组、链表、队列、栈②非线性表：二叉树、堆、图
2.连续的内存空间和相同类型的数据
3.时间复杂度
插入删除O(n)
查找O(1)
链表
LRU 缓存淘汰算法
先进先出策略 FIFO（First In，First Out）
最少使用策略 LFU（Least Frequently Used）
最近最少使用策略 LRU（Least Recently Used）
单链表
1.链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”
2.每个结点除了存储数据之外，还需要记录链上的下一个结点的地址，记录下个结点地址的指针叫作后继指针 next
3.第一个结点叫作头结点，头结点用来记录链表的基地址。
4.最后一个结点叫作尾结点，尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
5.时间复杂度
插入删除O(1)
查找O(n)
循环链表
1.循环链表是一种特殊的单链表
2.尾结点指针是指向链表的头结点
双向链表
1.每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点
双向环链表
链表VS数组
1插入删除：数组O(n)链表O(1)
2随机访问：数组O(1)链表O(n)
编写链表代码技巧
技巧一：理解指针或引用的含义
技巧二：警惕指针丢失和内存泄漏
技巧三：利用哨兵简化实现难度
技巧四：重点留意边界条件处理
技巧五：举例画图，辅助思考
技巧六：多写多练，没有捷径
常见的链表操作
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点
栈
特性
1.后进者先出，先进者后出，这就是典型的“栈”结构
2.一种“操作受限”的线性表
3.用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
栈在函数调用中的应用
栈在表达式求值中的应用
栈在括号匹配中的应用
队列
1.先进者先出，这就是典型的“队列”
2.操作受限的线性表数据结构
3.用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
循环队列
阻塞队列和并发队列
递归
递归需要满足的三个条件
1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件
如何编写递归代码？
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
递归注意事项
1.递归代码要警惕堆栈溢出
2.递归代码要警惕重复计算
怎么将递归代码改写为非递归代码？
排序
如何分析一个“排序算法”
执行效率
1. 最好情况、最坏情况、平均情况时间复杂度
2. 时间复杂度的系数、常数 、低阶
3. 比较次数和交换（或移动）次数
内存消耗
1. 通过空间复杂度衡量内存的消耗
2. 原地排序算法，就是特指空间复杂度是 O(1) 的排序算法
稳定性
1. 如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变
冒泡排序（Bubble Sort）
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
最好情况时间复杂度O(n)
最坏情况复杂度O(n²)
平均时间复杂度
推理方式
有序度：数组中具有有序关系的元素对的个数
逆序度：逆序度的定义正好跟有序度相反
满有序度：完全有序的数组的有序度
公式：n*(n-1)/2
公式：逆序度 = 满有序度 - 有序度
复杂度O(n²)
操作原子，比较和交换
插入排序（Insertion Sort）
将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
平均时间复杂度O(n²)
操作原子，比较和移动
选择排序（Selection Sort）
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
最好情况时间复杂度O(n²)
归并排序（Merge Sort）
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
分治思想
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了
性能分析
稳定的排序算法
最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)
空间复杂度是 O(n)，非原地排序
重点
理解递推公式和 merge() 合并函数
快速排序（Quick Sort）
快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
原地、不稳定
时间复杂度也是 O(nlogn)
理解递推公式和 partition() 分区函数
线性排序
桶排序（Bucket sort）
桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序（Counting sort）
计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
基数排序（Radix sort）
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了
线性时间复杂度可以达到 O(n)
排序优化
如何选择合适的排序算法？
1.一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数
如何优化快速排序？
原因：O(n2) 时间复杂度出现的主要原因还是因为我们分区点选的不够合理。
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
区分算法
1. 三数取中法
2. 随机法
qsort() 函数分析
二分查找（Binary Search）
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
时间复杂度O(logn)
实现
容易出错的3个地方
1. 循环退出条件
2.mid 的取值
3.low 和 high 的更新
非递归
应用场景的局限性
1.二分查找依赖的是顺序表结构，简单点说就是数组。
2.二分查找针对的是有序数据。
3.数据量太大也不适合二分查找。
四种二分查找的变形问题
变体一：查找第一个值等于给定值的元素
变体二：查找最后一个值等于给定值的元素
变体三：查找第一个大于等于给定值的元素
变体四：查找最后一个小于等于给定值的元素
跳表（Skip list）
链表加多级索引的结构，就是跳表
散列表（Hash Table）
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
散列函数
顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数设计的基本要求
1.散列函数计算得到的散列值是一个非负整数；
2.如果 key1 = key2，那 hash(key1) == hash(key2)；
3.如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
著名的哈希算法
MD5、SHA、CRC
散列冲突解决方法
开放寻址法（open addressing）
线性探测（Linear Probing）
二次探测（Quadratic probing）
双重散列（Double hashing）
链表法（chaining）
装载因子：散列表的装载因子=填入表中的元素个数/散列表的长度
如何设计散列函数？
1.散列函数的设计不能太复杂。
2.散列函数生成的值要尽可能随机并且均匀分布
装载因子过大了怎么办？
影响：装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
动态散列表
动态扩容：当装载因子过大时，重新申请一个更大的散列表，将数据搬移到这个新散列表中。
动态缩容：随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多，装载因子小于某个值之后，启动缩容
如何避免低效地扩容？
1.当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
2.当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。
如何选择冲突解决方法？
1. 开放寻址法（当数据量比较小、装载因子小的时候，适合采用开放寻址法。）
2. 链表法（基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。）
工业级的散列表应该具有哪些特性？
1.支持快速的查询、插入、删除操作；
2.内存占用合理，不能浪费过多的内存空间；
3.性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。
如何实现这样一个工业级散列表呢？
1.设计一个合适的散列函数；
2.定义装载因子阈值，并且设计动态扩容策略；
3.选择合适的散列冲突解决方法。
哈希算法
任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法
设计优秀哈希算法要求
从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同
散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
应用范围
应用一：安全加密
应用二：唯一标识
应用三：数据校验
应用四：散列函数
应用五：负载均衡
我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
应用六：数据分片
1. 如何统计“搜索关键词”出现的次数？
难点
第一个是搜索日志很大，没办法放到一台机器的内存中。
第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。
解决思路
可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。
2. 如何快速判断图片是否在图库中？
应用七：分布式存储
一致性哈希算法
其他:网络协议中的 CRC 校验、Git commit id 等等
二叉树
0 条评论
回复 删除
下一页
