考研复试 算法设计与分析 笔试之名词解释
布什戈门，真的要考这些东西啊？
名词解释
算法
对特定问题求解步骤的描述，是指令的有限序列。
算法的五个特征
- 输入：零个或多个输入。
- 输出：至少有一个输出。
- 有穷性：执行有限步后终止。
- 确定性：每条指令必须有确切的含义，无二义性。
- 可行性：每条指令必须足够基本，可以通过将已实现的基本运算执行有限次来完成。
算法复杂度
对算法效率的一种度量，通常分为时间复杂度和空间复杂度。
时间复杂度
描述算法运行时间随输入规模增长的增长速度，通常用大O符号表示。
空间复杂度
表示算法执行过程中所需要的额外空间随输入规模增长的增长速度。
归纳法
基于数学归纳法。
对于一个带有参数的问题，如果我们知道如何求解带有参数小于的问题，那么我们的任务就化为如何把解法扩展到带有参数的问题。
最优子结构
一个问题的最优解包含其子问题的最优解。
贪心算法
在每一步选择时只关注局部最优解，并希望通过每次所做的局部最优解产生全局最优解。
问题特征
最优子结构、贪心选择性质
常见应用
活动选择、哈夫曼编码、最小生成树
分治法
将问题分解为多个独立的子问题，分别求解子问题，再将其解合并成原问题的解。
常见应用
快速排序、归并排序、二分查找
实例解释：二分搜索
给定排好序的个元素，在这个元素找出一特定元素
取中间元素与进行比较：
- 如果等于中间元素，算法停止；
- 如果小于中间元素，则在序列的左半部分继续分治操作；
- 如果大于中间元素，则在序列的右半部分继续分治操作。
实例解释：合并排序
将待排序数组分成两半，递归地分别对每一半进行排序。将已有序的子序列合并，得到完全有序的序列。
动态规划
将问题分解为多个重叠的子问题，通过存储子问题的解来避免重复计算，从而提高效率。
问题特征
最优子结构、重叠子问题
四个核心步骤
- 定义子问题、表示状态
- 建立状态转移方程
- 初始化边界条件
- 填充状态表
常见应用
0/1背包、最长公共子序列、矩阵链乘
对比分治法和动态规划
- 分治法解决的是相互独立的子问题，动态规划解决的是重叠子问题。
- 分治法通常通过递归实现，动态规划通常通过迭代实现。
对比备忘录法和动态规划
- 备忘录法采用递归方式，自顶向下解决问题，并结合记忆化技术避免重复计算。
- 动态规划法采用迭代方式，自底向上解决问题。
回溯法
目标：可行解
采用深度优先遍历产生状态空间树的结点，在每个决策点尝试所有可能的选择，如果满足约束条件，就进入下一步选择；如果产生冲突，就回退到上一步并尝试其他选择。
分支限界法
目标：最优解
采用广度优先遍历产生状态空间树的结点，并利用问题的上下界信息剪枝，提高算法效率。
对比回溯法和分支限界法
回溯法的目标是找可行解，系统地尝试所有可能解。
分支限界法的目标是找最优解，通过剪枝策略减少搜索空间。
子集树和排列树
子集树：当问题是从个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。
排列树：当问题是要求出个元素满足某种性质的排列时，相应的解空间树称为排列树。
随机算法
执行过程中依赖随机选择的算法。
对于相同的输入，随机算法每次都可能产生不同的输出。
常见的随机算法：蒙特卡罗算法、拉斯维加斯算法。
蒙特卡罗算法特点
不保证解的正确性，但运行时间固定或可预期。
拉斯维加斯算法特点
保证解的正确性，但运行时间不固定。
衡量近似算法性能的标准
- 时间复杂性，必须是多项式阶，这是设计近似算法的基本目标。
- 解的近似程度。