数据结构和算法
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%准确
崔仔不一定真的准确
布隆过滤器
散列表+双向链表
O(1)查找和插入
LRU Cache
其他
O(1)随机访问
平均O(n)插入和删除
可被缓存加速访问
数组
顺序存储
不支持随机访问
O(1)插入和删除
O(n)访问某个元素
比数组占用更多存储空间
单向链表
每个节点多了指向前一个节点的指针
双向链表
尾节点指针指向头节点
循环链表
用数组描述的链表
静态链表
链表
链式存储
存储结构
后进先出
O(1)入栈出栈
特点
浏览器前进后退
括号匹配
表达式计算
应用
栈
先进先出
O(1)入队出队
操作有限资源
普通队列
入口和出口都可以入队和出队
双边队列
根据优先级出队
优先级队列
队列
线性结构
O(1)插入、删除、查询
安全加密
唯一标识
数据校验
散列函数
负载均衡
分布式存储
散列表
广度优先
前序遍历
中序遍历
后序遍历
深度优先
遍历
插入、删除、查找都比较快
红黑树
AVL树
平衡二叉树
形态
二叉树
B数
B+树
2-3树
2-3-4树
多数查找树
大顶堆
小顶堆
通常用数组实现
堆（堆是一个interface，实现有很多种，通常被看做完全二叉树，并用数组实现，所以暂放在此分支下）
树
顺序：邻接矩阵
链式：邻接表
存储
拓扑排序
最短路径
关键路径
最小生成树
二分图
最大流
图
非线性结构
逻辑结构
数据结构和算法
收藏
职业：开发
0 条评论
回复 删除
下一页
