2021年软件设计师考点：算法基础及常见算法

【考法分析】

本考点的考查形式主要有：根据题干的情景描述，判断所使用的算法策略；判断算法相关描述是否正确；下午题也会考查根据题干说明和代码，判断算法策略。

【要点分析】

1、算法的特性：

（1）有穷性：执行有穷步之后结束。

（2）确定性：算法中每一条指令都必须有确切的含义，不能含糊不清。

（3）输入（>=0）

（3）输出（>=1）

（4）有效性(可行性)：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0，b/a就无效。

2、分治法

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

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

3、动态规划法（用于求最优解）

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

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

4、回溯法

（1）特征：系统的搜索一个问题的所有解或任一解。有试探和回退的过程。

（2）经典问题：N皇后问题、迷宫、背包问题。

5、贪心法（用于求满意解）

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

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

【备考点拨】

1、掌握算法的特性、概念；

2、掌握常见算法的特点、适用场景，并能够加以区分。