常见算法及其特点

常见算法及其特点

算法是解决问题的步骤和方法，不同算法适用于不同场景。以下是常见的算法分类及其特点：

一、排序算法

1. 冒泡排序（Bubble Sort）

• 特点：
  • 比较相邻元素，交换逆序对。
  • 时间复杂度：O(n²)（最坏和平均），O(n)（最好，已排序时）。
  • 空间复杂度：O(1)（原地排序）。
  • 稳定性：稳定（相等元素不交换）。
• 适用场景：教学示例，小规模数据排序。

2. 选择排序（Selection Sort）

• 特点：
  • 每次选择未排序部分的最小值放到已排序末尾。
  • 时间复杂度：O(n²)（所有情况）。
  • 空间复杂度：O(1)。
  • 稳定性：不稳定（可能交换相等元素）。
• 适用场景：简单实现，对稳定性无要求的小数据。

3. 插入排序（Insertion Sort）

• 特点：
  • 将未排序元素插入到已排序部分的正确位置。
  • 时间复杂度：O(n²)（最坏和平均），O(n)（最好，已排序时）。
  • 空间复杂度：O(1)。
  • 稳定性：稳定。
• 适用场景：小规模数据或基本有序数据。

4. 快速排序（Quick Sort）

• 特点：
  • 分治思想：选基准值（pivot），划分小于和大于基准的部分。
  • 时间复杂度：O(n log n)（平均），O(n²)（最坏，如已排序数据且选第一个为基准）。
  • 空间复杂度：O(log n)（递归栈）。
  • 稳定性：不稳定（可能交换相等元素）。
• 适用场景：通用排序，大数据量高效。

5. 归并排序（Merge Sort）

• 特点：
  • 分治思想：递归拆分数组，合并已排序子数组。
  • 时间复杂度：O(n log n)（所有情况）。
  • 空间复杂度：O(n)（需要额外空间）。
  • 稳定性：稳定。
• 适用场景：需要稳定排序或链表排序。

6. 堆排序（Heap Sort）

• 特点：
  • 利用最大堆（或最小堆）逐步取出最大（最小）元素。
  • 时间复杂度：O(n log n)（所有情况）。
  • 空间复杂度：O(1)（原地排序）。
  • 稳定性：不稳定。
• 适用场景：需要 O(1) 空间且要求 O(n log n) 时间的场景。

二、搜索算法

1. 线性搜索（Linear Search）

• 特点：
  • 逐个检查元素直到找到目标。
  • 时间复杂度：O(n)（最坏和平均）。
  • 空间复杂度：O(1)。
• 适用场景：无序数据或小规模数据。

2. 二分搜索（Binary Search）

• 特点：
  • 在有序数组中，每次比较中间元素缩小搜索范围。
  • 时间复杂度：O(log n)。
  • 空间复杂度：O(1)（迭代实现）或 O(log n)（递归实现）。
• 适用场景：有序数组的高效搜索。

3. 深度优先搜索（DFS, Depth-First Search）

• 特点：
  • 递归或栈实现，优先探索子节点。
  • 时间复杂度：O(V + E)（V 是顶点数，E 是边数）。
  • 空间复杂度：O(V)（递归栈）。
• 适用场景：图/树的遍历、路径搜索、拓扑排序。

4. 广度优先搜索（BFS, Breadth-First Search）

• 特点：
  • 队列实现，逐层探索节点。
  • 时间复杂度：O(V + E)。
  • 空间复杂度：O(V)（队列）。
• 适用场景：最短路径问题（如无权图）、层次遍历。

三、图算法

1. Dijkstra 算法

• 特点：
  • 单源最短路径（边权非负）。
  • 时间复杂度：O((V + E) log V)（优先队列优化）。
• 适用场景：地图导航、网络路由。

2. Floyd-Warshall 算法

• 特点：
  • 多源最短路径（可处理负权边，但不能有负环）。
  • 时间复杂度：O(V³)。
• 适用场景：所有节点对的最短路径问题。

3. Kruskal 算法

• 特点：
  • 最小生成树（基于并查集优化）。
  • 时间复杂度：O(E log E)（排序边）。
• 适用场景：网络设计、电路布线。

4. Prim 算法

• 特点：
  • 最小生成树（基于优先队列优化）。
  • 时间复杂度：O(E log V)。
• 适用场景：与 Kruskal 类似，适合稠密图。

四、动态规划（Dynamic Programming, DP）

特点：

• 分治 + 记忆化：将问题分解为子问题，存储子问题解避免重复计算。
• 时间复杂度：取决于子问题数量和状态转移方程。
• 适用场景：
  • 最优子结构问题（如背包问题、最长公共子序列）。
  • 重叠子问题（如斐波那契数列）。

经典问题：

• 斐波那契数列（优化后 O(n)）。
• 0-1 背包问题。
• 最长公共子序列（LCS）。

五、贪心算法（Greedy Algorithm）

特点：

• 局部最优选择：每一步选择当前最优解，希望达到全局最优。
• 时间复杂度：通常较低（如排序后 O(n)）。
• 适用场景：
  • 问题具有贪心选择性质（如霍夫曼编码、活动选择问题）。
  • 注意：不一定总能得到全局最优解（如部分背包问题）。

六、分治算法（Divide and Conquer）

特点：

• 分解 + 解决 + 合并：将问题分解为子问题，递归解决后合并结果。
• 时间复杂度：通常为 O(n log n)（如快速排序、归并排序）。
• 适用场景：
  • 可分解的问题（如排序、矩阵乘法、最近点对问题）。

七、回溯算法（Backtracking）

特点：

• 尝试 + 撤销：逐步构建解，失败时回退到上一步。
• 时间复杂度：通常较高（指数级，如全排列问题）。
• 适用场景：
  • 组合问题（如八皇后、数独、组合总和）。
  • 需要穷举所有可能解的场景。

八、字符串算法

1. KMP 算法

• 特点：
  • 字符串匹配（避免不必要的回溯）。
  • 时间复杂度：O(m + n)（m 是模式串长度，n 是文本长度）。
• 适用场景：高效字符串搜索（如 DNA 序列匹配）。

2. Manacher 算法

• 特点：
  • 最长回文子串（线性时间）。
  • 时间复杂度：O(n)。
• 适用场景：回文相关问题。

九、其他经典算法

1. 并查集（Disjoint Set Union, DSU）

• 特点：动态连通性管理（高效合并与查询集合）。
• 时间复杂度：接近 O(1)（路径压缩 + 按秩合并优化）。
• 适用场景：图的连通分量、Kruskal 算法。

2. 哈希算法（Hashing）

• 特点：快速查找（如布隆过滤器、哈希表）。
• 时间复杂度：平均 O(1)。
• 适用场景：字典、缓存、去重。

总结对比

选择建议：

• 排序：大数据量用快速排序/归并排序，小数据用插入排序。
• 搜索：有序数据用二分搜索，图/树用 DFS/BFS。
• 图问题：最短路径用 Dijkstra，最小生成树用 Kruskal/Prim。
• 动态规划：最优子结构问题（如背包、LCS）。
• 贪心算法：局部最优可导致全局最优的问题（如活动选择）。
• 回溯算法：需要穷举所有解的组合问题（如八皇后）。