数据结构和算法
2024-04-19 11:09:08 1 举报AI智能生成
数据结构和算法梳理
作者其他创作
大纲/内容
复杂度分析
时间复杂度
分析
最好
最坏
平均
均摊
常见时间复杂度
O(1)散列表
O(log n)二分查找、二叉搜索树
O(n)大多数遍历
O(n^2)双重循环
O(2^n)递归
空间复杂度
O(1)原地操作
O(n)开辟线性辅助空间
排序
O(n^2)
冒泡排序
选择排序
插入排序
希尔排序
O(nlogn)
归并排序
快速排序
堆排序
O(n)
基数排序
计数排序
桶排序
字符串匹配
朴素
RK
BM
KMP
Trie
AC自动机
后缀数组
查找
线性表查找
树结构查找
散列表查找
搜索
深度优先搜索
广度优先搜索
A*启发式搜索
算法思想
贪心算法
分治算法
动态规划
回溯算法
枚举算法
其他
位运算
熟记常见的位运算公式
布隆过滤器
多个hash函数映射到多个位上
不存在100%准确
崔仔不一定真的准确
LRU Cache
散列表+双向链表
O(1)查找和插入
存储结构
顺序存储
数组
O(1)随机访问
平均O(n)插入和删除
可被缓存加速访问
链式存储
链表
单向链表
不支持随机访问
O(1)插入和删除
O(n)访问某个元素
比数组占用更多存储空间
双向链表
每个节点多了指向前一个节点的指针
循环链表
尾节点指针指向头节点
静态链表
用数组描述的链表
逻辑结构
线性结构
栈
特点
后进先出
O(1)入栈出栈
应用
浏览器前进后退
括号匹配
表达式计算
队列
普通队列
特点
先进先出
O(1)入队出队
应用
LRU Cache
操作有限资源
双边队列
入口和出口都可以入队和出队
优先级队列
根据优先级出队
非线性结构
散列表
O(1)插入、删除、查询
应用
安全加密
唯一标识
数据校验
散列函数
负载均衡
分布式存储
树
二叉树
遍历
广度优先
深度优先
前序遍历
中序遍历
后序遍历
形态
平衡二叉树
插入、删除、查找都比较快
应用
红黑树
AVL树
多数查找树
B数
B+树
2-3树
2-3-4树
堆（堆是一个interface，实现有很多种，通常被看做完全二叉树，并用数组实现，所以暂放在此分支下）
大顶堆
小顶堆
通常用数组实现
图
存储
顺序：邻接矩阵
链式：邻接表
拓扑排序
最短路径
关键路径
最小生成树
二分图
最大流
收藏
职业：开发
0 条评论
下一页
