# 算法设计方法
# 蛮力法（Brute-force）
- 简介：这是一种最直接、最简单的算法设计方法，通常基于问题的描述和所涉及的概念来直接构造算法。
# 分治法（Divide and Conquer）
- 简介：将一个大问题分解成若干个相互独立、规模较小的子问题，递归地解决这些子问题，然后将子问题的解合并，以得到原问题的解。
- 典型应用：快速排序、二叉树遍历、大整数乘法、矩阵乘法、快速傅里叶变换（FFT）。
# 减治法（Decrease and Conquer）
- 简介：将一个问题转化为一个或多个规模较小的同类子问题，通常只需要解决其中一个子问题，通过求解该子问题来得到原问题的解。
- 典型应用：折半查找、选择排序、辗转相除法、非线性方程的二分法。
- 简介：将一个难以直接求解的问题，通过某种变换（如改变问题表述、改变数据结构等），转换成一个更容易求解或有已知解法的问题。
- 典型应用：顺序查找、线性方程组的求解。
# 贪心算法（Greedy Algorithms）
- 简介：在每一步决策中都采取在当前看来最优的选择，期望通过局部最优解来达到全局最优解。
- 典型应用：最小生成树的 Prim 算法和 Kruskal 算法、单源最短路径的 Dijkstra 算法、Huffman 树及 Huffman 编码、最速下降法。
# 动态规划（Dynamic Programming）
- 简介：通过将复杂问题分解为相互重叠的子问题，并存储子问题的解，避免重复计算，从而高效地解决问题。
- 典型应用：背包问题、求解图的全源最短距离的 Floyd 算法、解卷积码的 Viterbi 算法。
# 搜索算法（Search Algorithms）
- 简介：系统地探索问题解空间，寻找满足特定条件的解。
- 回溯法（Backtracking）：一种通过递归探索所有可能解的方法，当发现当前路径无法通向有效解时，就回溯到上一步，尝试其他路径。
- 分支定界法（Branch and Bound）：一种用于优化问题的搜索算法，通过剪枝操作减少搜索空间，常用于解决组合优化问题。
# 随机算法（Randomized Algorithms）
- 简介：在算法设计中引入随机性，利用随机数来做出决策，以提高效率或简化设计。
- Sherwood 算法：通过引入随机性来消除或减少问题“好实例”与“坏实例”之间的差异。它不能避免算法的最坏情况发生，但能消除这种最坏情形与特定输入实例之间的关联性，使最坏情况在平均意义上变得不太可能。
- Las Vegas 算法：这类算法在求解过程中引入随机性决策，得到的解一定是正确的，但可能无法在所有情况下都找到解，或无法找到所有解。
- Monte Carlo 算法：一种基于概率的统计模拟方法，它不保证得到的解是正确的，但通过合理设计和大量重复测试，可以以高概率得到高精度的解。
# 算法优化技术
- 简介：通过预处理输入数据，在不改变数据本身的情况下，增加辅助信息或优化数据结构，以提高算法效率。
- 典型应用：字符串匹配的 KMP 算法、字符串匹配的 Horspool 算法、计数排序。
# 预构造技术（Prestructuring）
- 简介：在算法执行前，对数据进行预先组织和构造，以适应后续的操作，提高效率。
- 典型应用：二叉查找树、倒排索引、并查集、堆和堆排序。
# 时空平衡（Time-Space Trade-offs）
- 简介：一种设计思想，通过增加空间（内存）使用来减少时间（计算）开销，反之亦然。
- 典型应用：比特逆序、散列（哈希）。
# 算法的组合（Algorithm Combination）
- 简介：将多种算法或技术进行结合，以取长补短，解决更为复杂或特定场景的问题。
- 典型应用：利用插入排序改进快速排序、非线性方程的多种迭代求解方法、保护法。
# 计算复杂性理论简介
