数据结构与算法
2023-08-23 15:05:10 2 举报
AI智能生成
登录查看完整内容
数据结构与算法
作者其他创作
大纲/内容
存储特点
无限的输入值域,集中均匀的输出值域
相同的输入有相同的输出
不同的输入有不同或相同(哈希冲突)的输出
合理的混合函数
使用素数
使用位操作
考虑输入的所有部分
使用加密技术
避免冲突
使用随机化
设计原则
散列函数
线性探测法
开放地址法
再哈希法
链地址法
哈希冲突
基本组成
构造
判断值是否存在
处理误判
处理流程
算法实现
布隆过滤器(Bloom Filter)
子主题
应用实例
布谷鸟过滤器(Cuckoo Filter)
选取节点
添加节点
删除节点
虚拟节点
一致性哈希(Consistent Hashing)
追加写入
偏移量
分段压缩
文件格式
删除记录
崩溃恢复
部分写入
并发控制
哈希表必须全部放入内存
区间访问效率不高
局限性
哈希索引
找出出现次数最多的元素
找出重复的元素
最近最少使用(LRU)
最不经常使用(LFU)
淘汰算法
应用场景
哈希表(Hash Table)
避免越界
使用容器
使用哨兵
使用须知
访问效率
数组(Array)
链表(Linked List)
实现方式
栈(Stack)
队列(Queue)
查找
保持平衡
插入和删除
访问、存储效率
跳表(Skip List)
线性表(Linear List)
大顶堆/小顶堆(Max/Min Heap)
优先级队列(Priority Queue)
斐波那契堆(Fibonacci Heap)
二项堆(Binomial Heap)
索引堆(Index Heap)
找出出现次数最多的 N 个元素
堆(Heap)
找出指定范围内未出现的元素
找出指定范围内任意一个未出现的元素
找出出现 2 次的元素
位图(Bit Map)
平衡二叉搜索树(AVL)
插入节点
初步调整
二次调整
基本操作
红黑树(Red-Black Tree)
伸展树(Splay Tree)
树堆(Treap)
二叉搜索树(Binary Search Tree)
哈夫曼树(Huffman Tree)
线段树(Segment Tree)
二叉树(Binary Tree)
缩点优化
存储节点
内存消耗
实现
字典树(Trie)
Trie 树
失败指针
AC 自动机(AC Automaton)
区间查询
单点修改
树状数组(Binary Indexed Tree)
查询
合并
添加
并查集(Union Find)
与红黑树比较
支持范围访问
堆文件
聚簇索引
在索引中存储值
级联索引
多列索引
全文搜索和模糊索引
二级索引
分页设计
B+ 树
B* 树
更新
分裂
平衡
插入
预写日志
可靠性
写时复制
键略缩信息
相邻布局
添加额外指针
分形树
性能优化
读取较快
写入较慢
优势与劣势
B 树 / B+ 树
多叉树(Multi-Branch Tree)
压缩段
查找键
SSTables
处理写请求
处理读请求
合并和压缩
WAL
布隆过滤器
压缩合并策略
写放大
写入较快
读取较慢
更好的压缩
写入带宽开销
Cassandra、HBase
Elasticsearch、Solr
LSM 树(Log-Structured-Merge-Tree)
树(Tree)
邻接矩阵
邻接表
存储结构
路径
平行边
自环边
有/无环图
环
桥(Bridge)
简单图
连通分量
生成树/森林
连通图
边
相连/相连
入度(Indegree)/出度(Outdegree)
度
稀疏图/稠密图/完全图
割点(Articulation Points)
顶点
二分图
切分
同构图
完全图
有向图/无向图(Directed/Undirected)
有权图/无权图(Weighted/Unweighted)
基本概念
无权最短路径
状态转换
遍历树
广度优先遍历(BFS)
深度优先遍历(DFS)
回溯(Backtracking)
状态压缩(State Compress)
记忆化搜索(Memory Search)
哈密尔顿回路与路径(Hamilton Loop and Path)
无权图
Dijkstra 算法
SPFA 算法
Moore-Bellman-Ford 算法
Floyd 算法(所有点对)
最短路径(Shortest Path)
有权图
有向/无向图完全通用
Fleury 算法
Hierholzer 算法
欧拉回路与路径(Euler Loop and Path)
当前路径记录
深度优先遍历(后序的逆序)
拓扑排序(Topological Sorting)
环(Cycle)检测
Ford-Fulkerson 思想
Edmonds-Karp 算法
Dinic 算法
MPM 算法
最大流(Max Flow)
Push-relabel 算法
最小割(Min Cut)
网络流模型(Network Flow)
有向/无向图通用且有差别
寻找桥(边)与割点
泛洪填充(Flood Fill)
二分图(Bipartite Graph)
最大流算法(Max Flow)
Hungarian 算法
匹配问题(Matching)
Kruskal 算法
Prim 算法
Fredman-Tarjan 算法
Chazelle 算法
最小生成树(MST)
AOE 网
关键路径(Key Path)
无向图
Kosaraju 算法
强连通分量(Strongly Connected Components)
有向图
图(Graph)
机器学习
位运算
数论(Number Theory)
计算几何(Computation Geometry)
随机抽样
概率统计(Probability Statistics)
拓扑网络(Topology Network)
线性代数(Linear Algebra)
Fisher-Yates 算法
洗牌算法(Shuffle)
随机(Random)
数学(Math)
阻塞队列
CAS 原子操作
解决 ABA 问题
链表实现
数组实现
无锁队列
基本使用
串/并行操作
多生产者多消费者模型
进阶应用
RingBuffer
Sequence
Sequencer
Sequence Barrier
WaitStrategy
WorkProcessor
EventProcessor
核心组件
局部性原理
ArrayBlockingQueue
缓存行填充
伪共享
无锁算法
Disruptor
高性能队列
并行处理
贪心(Greedy)
问题特征
分治(Divide and Conquer)
多阶段决策最优解模型
最优子结构
无后效性
重复子问题
模型特征
状态转移表
状态转移方程
解题思路
单串
双串
矩阵
线性动态规划
前缀和
区间动态规划
背包问题
状态压缩
计数问题
矩阵快速幂
数位动态规划
常见类型
动态规划(Dynamic Programming)
枚举(Enumerating)
算法思想
大 O 复杂度表示法
1. 只关注循环执行次数最多的一段代码
2. 加法法则:总复杂度等于量级最大的代码的复杂度
3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
分析方法
O(1):不存在循环语句、递归语句
O(logn):二分查找
O(n):一层循环
O(nlogn):高级排序
O(m+n)、O(m*n):两个数据规模
O(n^2):排序
O(2^n):排列
...
常见的复杂度量级
最好、最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
复杂度分析
稳定性
有序度
最好/最坏/平均时间复杂度
时间复杂度的系数、常数 、低阶
比较次数和交换/移动次数
执行效率
分析维度
选择排序(Selection Sort)
堆排序(Heap Sort)
选择
冒泡排序(Bubble Sort)
鸡尾酒排序(Cocktail Shaker Sort)
快速排序(Quick Sort)
归并排序(Merge Sort)
交换
插入排序(Insertion Sort)
希尔排序(Shell Sort)
比较型(Comparation)
桶排序(Bucket Sort)
计数排序(Counting Sort)
基数排序(Radix Sort)
分配型(Distribution)
排序(Sort)
二分查找(Binary Search)
B 树(B Tree)
查找(Search)
BF
哈希函数
RK
BM
KMP
Sunday
单模式匹配
直接排序
DC3 算法
SA-IS 算法
子串查找
最长公共前缀
最长重复子串
后缀数组(Suffix Array)
多模式匹配
字符串匹配(String)
使用布隆过滤器判断某个元素已存在于集合
判断元素是否出现在集合中
1. 根据数据特征设计哈希函数,要将数据集均等划分。2. 使用哈希函数把数据集划分到多个小文件: 相同元素存在于同一文件、单个文件数据量 <= 数据集大小。3. 对每个小文件使用哈希表统计元素出现的个数。 根据每个小文件中的元素出现频度、求出现次数最多的元素。
1. 哈希函数把数据分流到多台机器上、用哈希函数拆分到多个小文件中;2. 对每个小文件,使用哈希表统计元素出现频率;3. 遍历哈希表,使用容量为 N 的小根堆收集 top N 元素;4. 对每个文件小根堆(top N)进行外部排序或使用小根堆处理,得到最终 top N。
找出出现次数最多的 N 个元素
1. 创建长度为数据集大小的位图,要求元素是非负整数,否则要做映射;2. 遍历数据集,元素值对应位图的下标,修改该位置的值为 1;3. 遍历位图,如某个位置上标记为 0,表示该元素在数据集中未出现。
1. 遍历数据集,根据元素的值,在区间计数数组上统计区间上元素个数;2. 遍历区间计数数组,找到值小于 n/k 的区间编号 i,定为目标区间;3. 遍历数据集,关注落在目标区间内的元素(num/(n/k) == i),位图位置 bitmap[num-(n/k)*i] 设为 1;4. 遍历位图找到未被设为 1 的位置 j,则 j+(n/k)*i 即为第一个未出现的元素。
使用哈希函数将元素分配到多台机器上,每台机器分别统计重复的值;或将大文件拆分成多个小文件,每个小文件再用哈希表遍历找到重复的值。
参考“找出指定范围内任意一个未出现的元素”的区间计数法:1. 遍历数据集,根据元素的值,在区间计数数组上统计区间上元素个数。2. 遍历计数数组,累计每个区间的计数,找出累计元素不过半与过半之间的区间编号(比如 40 个数,前 0~k-1 区间上有 18 个,加上第 k 区间后超过 20 个,可知第 20 个数在第 k 区间第 2 个)。3. 申请区间长度的数组,再次遍历数据集,关注出现在该区间的元素、做词频统计(找到该区间上的第 2 个元素)。
求中位数
数据倾斜
海量数据
算法
数据结构与算法
0 条评论
回复 删除
下一页