必须掌握的算法

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

1. 搜索算法

• 线性搜索：迭代地搜索数组中的每个元素。
  时间复杂度：O(n)

• 二分查找：将目标元素与已排序数组的中间元素进行比较，从而缩小搜索范围。
  时间复杂度：O(log₂n)

2. 排序算法

• 冒泡排序：通过重复遍历交换相邻元素。
  时间复杂度：O(n²)

• 插入排序：将元素插入到数组已排序部分的正确位置。
  时间复杂度：O(n²)

• 选择排序：每次遍历从未排序元素中选择最小值。
  时间复杂度：O(n²)

• 堆排序：使用堆对元素进行排序。
  时间复杂度：O(n log n)

• 归并排序：一种分治算法，它将数组分成两部分，分别对每一半进行排序，然后将两部分合并。
  时间复杂度：O(n log n)

• 快速排序：使用枢轴对数组进行划分并递归排序。
  时间复杂度：O(n log n)（平均），O(n²)（最坏情况）。

3. 基本数学算法

• 欧几里得算法求最大公约数：通过除法求最大公约数。
• 埃拉托色尼筛法：通过排除倍数来确定质数。
• 位操作：使用位运算符进行底层操作。

4. 图算法

• 广度优先搜索（BFS）：使用队列逐层遍历。
• 深度优先搜索（DFS）：使用堆栈逐层进行搜索。时间复杂度：O(V + E)
• D* ijkstra 算法： * 查找加权图中的最短路径。

5. 树算法

• 中序遍历：左子树→根树→右子树。
• 前序遍历：根节点 → 左子树 → 右子树。
• 后序遍历：左子树 → 右子树 → 根节点。时间复杂度：O(n)
• Kruskal 算法：通过按权重顺序添加边来找到最小生成树。

6. 动态规划

• Floyd-Warshall 算法：在加权图中寻找所有点对之间的最短路径。它结合了记忆化（自顶向下）和制表（自底向上）技术。

7. 回溯算法

• 解决诸如 N 皇后问题、子集求和问题、图着色问题和哈密顿回路问题等。

8. 霍夫曼压缩算法

• 通过构建霍夫曼树并根据频率为字符分配代码来压缩数据。