导图社区 经典算法有哪些
这是一个关于经典算法有哪些的思维导图,讲述了经典算法有哪些的相关故事,如果你对经典算法有哪些的故事感兴趣,欢迎对该思维导图收藏和点赞~
编辑于2020-11-22 21:53:57经典算法有哪些
排序算法
冒泡排序:通过相邻元素的比较和交换来对数据进行排序。时间复杂度为O(n^2)。
选择排序:每次从待排序的数据中选择最小的元素,并放在已排序部分的末尾。时间复杂度为O(n^2)。
插入排序:将数据分为已排序和未排序两部分,每次从未排序中取出一个元素插入到已排序中的适当位置。时间复杂度为O(n^2)。
快速排序:通过选择一个元素作为基准,将比基准小的元素放在基准的左边,比基准大的元素放在右边,然后对左右两部分递归执行相同的操作。时间复杂度为O(nlogn)。
归并排序:将待排序的数据不断拆分为两部分,排序后再将两部分合并。时间复杂度为O(nlogn)。
搜索算法
顺序搜索:按顺序逐个比较待搜索元素和数据中的元素,直到找到匹配或搜索结束。时间复杂度为O(n)。
二分搜索:将有序数据分成两部分,通过比较待搜索元素和中间元素的大小确定待搜索元素所在的部分,然后在该部分中继续进行二分搜索。时间复杂度为O(logn)。
广度优先搜索:从起始点开始,按照广度优先的顺序遍历图或树的节点,直到找到目标节点或遍历完所有节点。时间复杂度为O(V+E),其中V表示节点数,E表示边数。
深度优先搜索:从起始点开始,按照深度优先的顺序遍历图或树的节点,直到找到目标节点或遍历完所有节点。时间复杂度为O(V+E)。
图算法
最短路径算法
Dijkstra算法:求解图中的单源最短路径问题,针对非负权值图。时间复杂度为O(V^2)。
Bellman-Ford算法:求解图中的单源最短路径问题,可以处理包含负权值边的图。时间复杂度为O(V*E)。
Floyd-Warshall算法:求解图中的所有节点对之间的最短路径问题。时间复杂度为O(V^3)。
最小生成树算法
Kruskal算法:通过不断选择满足条件的边来构建最小生成树,适用于边稀疏的图。时间复杂度为O(ElogV)。
Prim算法:从一个节点开始,逐步扩展最小生成树,适用于边稠密的图。时间复杂度为O(V^2)。
查找算法
哈希查找:通过将关键字映射到哈希表中的位置来进行查找,时间复杂度为O(1)。
二叉搜索树查找:通过比较关键字和节点值的大小决定搜索方向,时间复杂度为O(logn)。
B树查找:通过多叉搜索树的方式进行查找,适用于高度平衡的数据结构,时间复杂度为O(logn)。
红黑树查找:一种自平衡的二叉搜索树,可以保持良好的查找性能,时间复杂度为O(logn)。
动态规划算法
背包问题:给定一组物品和一个背包容量,选择物品放入背包以使得价值最大化。时间复杂度为O(nW),其中n为物品数量,W为背包容量。
最长公共子序列:找到两个序列中的最长公共子序列。时间复杂度为O(mn),其中m和n分别为两个序列的长度。
最短路径问题:在给定的图中找出从起点到终点的最短路径。时间复杂度为O(V^2)。
最大子数组和:找到一个数组中和最大的连续子数组。时间复杂度为O(n),其中n为数组长度。
字符串匹配算法
暴力匹配算法:通过逐个比较文本和模式串中的字符来进行匹配。时间复杂度为O(n*m),其中n和m分别为文本和模式串的长度。
KMP算法:通过利用已经匹配过的信息来避免不必要的字符比较,提高匹配效率。时间复杂度为O(n+m),其中n和m分别为文本和模式串的长度。
Boyer-Moore算法:通过对模式串的右端进行比较,将模式串向右移动更多的位数,提高匹配效率。时间复杂度为O(n),其中n为文本的长度。