算法
2024-08-28 11:23:29
发布于：广东
14阅读
0回复
0点赞
这个算法是指 提高级要求掌握 的算法
1. 复杂度分析
-
空间复杂度分析：衡量算法在运行时所需的内存空间。主要包括额外空间（例如递归栈、临时存储）和输入数据本身的空间。
-
时间复杂度分析：衡量算法执行所需的时间。通常使用大O符号来表示，分析算法在最坏情况、平均情况和最好情况的时间复杂度。
2. 基础算法
- 分治算法：
- 描述：将问题分解成更小的子问题，递归解决这些子问题，然后合并它们的结果。
- 应用：快速排序、归并排序、二叉搜索树等。
3. 排序算法
-
归并排序：
- 描述：基于分治思想，将数组分成两半，分别排序，然后合并两个已排序的半部分。
- 时间复杂度：
- 空间复杂度：
-
快速排序：
- 描述：选择一个枢轴元素，将数组分成两部分，一部分比枢轴小，另一部分比枢轴大，然后递归排序。
- 时间复杂度：平均，最坏
- 空间复杂度：（递归栈空间）
-
堆排序：
- 描述：利用堆数据结构，首先构建一个大根堆（或小根堆），然后逐步取出最大（或最小）元素并调整堆。
- 时间复杂度：
- 空间复杂度：
-
- 描述：利用完全二叉树进行排序，先进行"锦标赛"决定胜者，然后输出排序结果。
- 时间复杂度：
- 空间复杂度：
-
桶排序：
- 描述：将元素分到不同的桶中，再对每个桶内的元素进行排序，最后合并桶中的元素。
- 时间复杂度：，为桶的数量
- 空间复杂度：
-
基数排序：
- 描述：按位处理数字，从最低位到最高位进行排序，通常利用桶排序作为子排序算法。
- 时间复杂度：，为位数
- 空间复杂度：
4. 字符串相关算法
- 字符串匹配算法 - KMP：
- 描述：通过预处理模式字符串，创建部分匹配表，来优化字符串匹配的过程。
- 时间复杂度：，为文本长度，为模式长度
5. 搜索算法
-
搜索的剪枝优化：通过剪枝操作减少搜索空间，提高搜索效率。
-
记忆化搜索：将子问题的结果缓存起来，以避免重复计算。
-
- 描述：使用启发式函数来估计距离目标的代价，从而优化搜索路径。
- 示例：A*搜索算法
-
双向宽度优先搜索：从起点和终点同时进行宽度优先搜索，直到两者相遇，从而缩短搜索路径。
-
选代加深搜索：结合深度优先搜索和宽度优先搜索，通过逐步增加搜索深度来找到解决方案。
-
搜索对象的压缩存储：压缩存储搜索空间中的数据以节省内存，提高效率。
6. 图论算法
-
- 描述：用于寻找最小生成树。
- 时间复杂度：Prim（），Kruskal（）
-
求次小生成树算法：在最小生成树的基础上，找出次小的生成树。
-
- 描述：用于求解单源最短路径。
- 时间复杂度：Dijkstra（），Bellman-Ford（），SPFA（通常为）
-
求单源次短路径算法：在单源最短路径基础上，寻找次短路径。
-
Floyd-Warshall 算法：用于求解任意两点间的最短路径及传递闭包。
- 时间复杂度：
-
- 描述：对有向无环图进行排序，使得每个顶点在其所有前驱顶点之后。
- 时间复杂度：
-
- 描述：欧拉道路经过每条边恰好一次，欧拉回路则是回到起点。
- 时间复杂度：
-
- 描述：通过染色方法或其他方法确定图是否为二分图。
- 时间复杂度：
-
- 描述：在树结构中，找到两个节点的最近公共祖先。
- 时间复杂度：（使用二进制提升方法）
-
- 描述：找到图中所有强连通分量。
- 时间复杂度：
-
强连通分量的缩点算法：将强连通分量缩减为单一节点，形成一个DAG。
-
- 描述：找到删除某个点或边会增加图的连通分量的点或边。
- 时间复杂度：（Tarjan算法）
有帮助，赞一个