经典算法有哪些

这是一个关于经典算法有哪些的思维导图，讲述了经典算法有哪些的相关故事，如果你对经典算法有哪些的故事感兴趣，欢迎对该思维导图收藏和点赞~

经典算法有哪些

• 排序算法
  • 冒泡排序：通过相邻元素的比较和交换来对数据进行排序。时间复杂度为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为文本的长度。