2021下半年软件设计师高频考点：数据结构与算法应用

常见算法特征总结

1、分治法

特征：把一个问题拆分成多个小规模的相同子问题，一般用递归解决。

经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、汉诺塔、大整数乘法。

2、动态规划法（用于求最优解）--“最优子结构”和递归式

特征：划分子问题，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

3、回溯法

特征：系统的搜索一个问题的所有解或任一解

经典问题：N皇后问题、迷宫、背包问题

4、贪心法（一般用于求满意解）

特征：局部最优，但整体不见得最优。每步有明确的，既定的策略。

经典问题：背包问题（如装箱）、多机调度、找零钱问题