数据结构常见算法流程图解
2025-04-14 19:19:21 0 举报AI智能生成
数据结构常见算法流程图解
作者其他创作
大纲/内容
算法基础
时间复杂度
大O表示法
描述算法运行时间的增长趋势
与输入数据量n的关系
常见时间复杂度
O(1) 常数时间
O(log n) 对数时间
O(n) 线性时间
O(n log n) 线性对数时间
O(n^2) 平方时间
空间复杂度
衡量算法占用存储空间的大小
与输入数据量n的关系
排序算法
冒泡排序
比较相邻元素
交换顺序错误的元素
重复过程
直到无元素交换，完成排序
选择排序
找到最小元素
与第一个位置交换
接着找到剩余元素的最小值
与第二个位置交换
重复过程
直到所有元素排序完成
插入排序
将数组分为已排序和未排序两部分
从未排序部分取出元素
将取出的元素插入已排序部分的适当位置
重复过程直到所有元素排序
快速排序
选择基准值
分区操作
小于基准值的元素移到左边
大于基准值的元素移到右边
递归排序左右子数组
直到子数组只有一个元素或为空
归并排序
分割数组
直到每个子数组只有一个元素
合并子数组
按顺序合并为一个有序数组
堆排序
构建最大堆
父节点大于子节点
交换堆顶元素与最后一个元素
调整剩余元素形成新的堆
重复过程
直到堆中只剩一个元素
搜索算法
线性搜索
从数组的一端开始
逐个检查每个元素
直到找到目标值或遍历完数组
返回找到的位置或-1表示未找到
二分搜索
在有序数组中进行
比较中间元素与目标值
若中间元素等于目标值
返回中间元素的索引
若中间元素大于目标值
在左半部分继续搜索
若中间元素小于目标值
在右半部分继续搜索
重复过程
直到找到目标值或区间为空
图算法
深度优先搜索（DFS）
从一个节点开始
访问所有可达节点
使用递归或栈实现
标记已访问节点以避免重复
广度优先搜索（BFS）
从一个节点开始
访问所有邻接节点
使用队列实现
按访问顺序逐层遍历图
最短路径算法
Dijkstra算法
找到最短路径树
记录从起点到每个节点的最短距离
Bellman-Ford算法
处理负权边
可以检测负权回路
Floyd-Warshall算法
计算所有节点对之间的最短路径
动态规划方法
树算法
二叉树遍历
前序遍历
访问根节点> 左子树> 右子树
中序遍历
左子树> 访问根节点> 右子树
后序遍历
左子树> 右子树> 访问根节点
二叉搜索树（BST）
插入操作
比较节点值
左子树小于根节点
右子树大于根节点
删除操作
处理三种情况
被删除节点无子节点
被删除节点有一个子节点
被删除节点有两个子节点
平衡树
AVL树
自平衡二叉搜索树
任何节点的两个子树的高度差不超过1
红黑树
自平衡二叉搜索树
满足特定的红黑性质
哈希算法
哈希函数
将输入（或“键”）映射到整数
用于快速查找数据
哈希表
基于数组实现
使用哈希函数计算索引
解决冲突
开放寻址法
线性探测、二次探测、双重哈希
链表法
每个数组位置存储一个链表
哈希应用
数据库索引
缓存机制
数据完整性检测
动态规划
重叠子问题
子问题在计算过程中重复出现
保存子问题的解以避免重复计算
最优子结构
问题的最优解包含其子问题的最优解
通过子问题的解构建原问题的解
动态规划示例
斐波那契数列
使用动态规划避免重复计算
背包问题
计算不超过背包容量的最大价值
最长公共子序列（LCS）
找出两个序列的最长公共子序列
贪心算法
局部最优选择
每一步选择当前看起来最优的方案
不保证全局最优解
贪心算法示例
最小生成树
Kruskal算法
按边权重顺序选择边
单源最短路径
Dijkstra算法
选择当前距离最近的未访问节点
货币找零问题
选择最大面额的硬币
重复直到凑足总金额
回溯算法
试错法
尝试所有可能的解决方案
一旦发现当前解决方案不可能成功
回退并尝试其他可能
回溯算法示例
八皇后问题
在8x8棋盘上放置八个皇后
使它们互不攻击
图的着色问题
使用最少的颜色为图着色
邻接节点颜色不同
组合问题
生成所有可能的组合
如从n个不同元素中取出k个元素的组合
0 条评论
下一页
