算法图解
coderljw 2024-10-13 大约 4 分钟
# 1. 算法简介
大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。
大 O 表示法指的并非以秒为单位的速度。大 O 表示法让你能够比较操作数，它指出了算法运行时间的增速。
一些常见的大 O 运行时间。
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法包括第 4 章将介绍的快速排序 —— 一种速度较快的排序算法。
- O(n 2 )，这样的算法包括第 2 章将介绍的选择排序 —— 一种速度较慢的排序算法。
- O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案 —— 一种非常慢的算法。
小结：
- 二分查找的速度比简单查找快得多。
- O(log n)比 O(n)快。需要搜索的元素越多，前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大 O 表示法表示。
# 2. 选择排序
小结：
- 数组的元素都在一起。
- 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
# 3. 快速排序
小结：
- D&C 将问题逐步分解。使用 D&C 处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
- 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为 O(n log n)。
- 大 O 表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
# 4. 散列表
小结：
- 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
- 散列表的查找、插入和删除速度都非常快。
- 散列表适合用于模拟映射关系。
- 一旦填装因子超过 0.7，就该调整散列表的长度。
- 散列表可用于缓存数据（例如，在 Web 服务器上）。
- 散列表非常适合用于防止重复。
# 5. 广度优先搜索
广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！
小结：
- 广度优先搜索指出是否有从 A 到 B 的路径。
- 如果有，广度优先搜索将找出最短路径。
- 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。
- 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
- 对于检查过的人，务必不要再去检查，否则可能导致无限循环。
# 6. 狄克斯特拉算法
狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径！
不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法 —— 贝尔曼 - 福德算法。
小结：
- 广度优先搜索用于在非加权图中查找最短路径。
- 狄克斯特拉算法用于在加权图中查找最短路径。
- 仅当权重为正时狄克斯特拉算法才管用。
- 如果图中包含负权边，请使用贝尔曼 - 福德算法。
# 7. 贪婪算法
贪婪算法：每步都采取最优的做法。
小结：
- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
- 对于 NP 完全问题，还没有找到快速解决方案。
- 面临 NP 完全问题时，最佳的做法是使用近似算法。
- 贪婪算法易于实现、运行速度快，是不错的近似算法。
# 8. 动态规划
动态规划先解决子问题，再逐步解决大问题。
小结：
- 需要在给定约束条件下优化某种指标时，动态规划很有用。
- 问题可分解为离散子问题时，可使用动态规划来解决。
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。
- 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式。
