布什戈门，真的要考这些东西啊？

名词解释

算法

对特定问题求解步骤的描述，是指令的有限序列。

算法的五个特征

1. 输入：零个或多个输入。
2. 输出：至少有一个输出。
3. 有穷性：执行有限步后终止。
4. 确定性：每条指令必须有确切的含义，无二义性。
5. 可行性：每条指令必须足够基本，可以通过将已实现的基本运算执行有限次来完成。

算法复杂度

对算法效率的一种度量，通常分为时间复杂度和空间复杂度。

时间复杂度

描述算法运行时间随输入规模增长的增长速度，通常用大O符号表示。

空间复杂度

表示算法执行过程中所需要的额外空间随输入规模增长的增长速度。

归纳法

基于数学归纳法。
对于一个带有参数$n$的问题，如果我们知道如何求解带有参数小于$n$的问题，那么我们的任务就化为如何把解法扩展到带有参数$n$的问题。

最优子结构

一个问题的最优解包含其子问题的最优解。

贪心算法

在每一步选择时只关注局部最优解，并希望通过每次所做的局部最优解产生全局最优解。

问题特征

最优子结构、贪心选择性质

常见应用

活动选择、哈夫曼编码、最小生成树

分治法

将问题分解为多个独立的子问题，分别求解子问题，再将其解合并成原问题的解。

常见应用

快速排序、归并排序、二分查找

实例解释：二分搜索

给定排好序的$n$个元素，在这$n$个元素找出一特定元素$x$
取中间元素与$x$进行比较：
如果$x$等于中间元素，算法停止；
如果$x$小于中间元素，则在序列的左半部分继续分治操作；
如果$x$大于中间元素，则在序列的右半部分继续分治操作。

实例解释：合并排序

将待排序数组分成两半，递归地分别对每一半进行排序。将已有序的子序列合并，得到完全有序的序列。

动态规划

将问题分解为多个重叠的子问题，通过存储子问题的解来避免重复计算，从而提高效率。

问题特征

最优子结构、重叠子问题

四个核心步骤

1. 定义子问题、表示状态
2. 建立状态转移方程
3. 初始化边界条件
4. 填充状态表

常见应用

0/1背包、最长公共子序列、矩阵链乘

对比分治法和动态规划

1. 分治法解决的是相互独立的子问题，动态规划解决的是重叠子问题。
2. 分治法通常通过递归实现，动态规划通常通过迭代实现。

对比备忘录法和动态规划

1. 备忘录法采用递归方式，自顶向下解决问题，并结合记忆化技术避免重复计算。
2. 动态规划法采用迭代方式，自底向上解决问题。

回溯法

目标：可行解
采用深度优先遍历产生状态空间树的结点，在每个决策点尝试所有可能的选择，如果满足约束条件，就进入下一步选择；如果产生冲突，就回退到上一步并尝试其他选择。

分支限界法

目标：最优解
采用广度优先遍历产生状态空间树的结点，并利用问题的上下界信息剪枝，提高算法效率。

对比回溯法和分支限界法

回溯法的目标是找可行解，系统地尝试所有可能解。
分支限界法的目标是找最优解，通过剪枝策略减少搜索空间。

子集树和排列树

子集树：当问题是从$n$个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。
排列树：当问题是要求出$n$个元素满足某种性质的排列时，相应的解空间树称为排列树。

随机算法

执行过程中依赖随机选择的算法。
对于相同的输入，随机算法每次都可能产生不同的输出。
常见的随机算法：蒙特卡罗算法、拉斯维加斯算法。

蒙特卡罗算法特点

不保证解的正确性，但运行时间固定或可预期。

拉斯维加斯算法特点

保证解的正确性，但运行时间不固定。

衡量近似算法性能的标准

1. 时间复杂性，必须是多项式阶，这是设计近似算法的基本目标。
2. 解的近似程度。