算法设计与分析（基础）

一、 算法的定义与特征，算法设计的基本步骤

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

五大特征：

• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。
• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
• 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
• 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

算法设计的基本步骤：
1．理解问题 2．建立数学模型 3. 算法设计与选择
4. 确定适当的数据结构 5．描述算法 6. 算法分析
7．实现与调试 8．分析算法的效率 9．算法的改进

二、 算法分析的目的是什么？如何评价算法，如何度量算法的复杂性？

目的：评估算法的效率（时间、空间）与适用性。

评价指标：

• 正确性：能否解决问题。

• 可读性：代码清晰易懂。

• 健壮性：处理异常输入的能力。

• 效率：时间复杂度和空间复杂度。

复杂度度量：

• 时间复杂度：用大O表示法描述输入规模与运行时间的关系
• 空间复杂度：算法所需内存空间

三、 递归算法、分治法、贪婪法、动态规划法、回溯法的基本思想方法。

• 递归算法

递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己

设计思路：
⑴ 边界条件：确定递归到何时终止；
⑵ 递归模式：大问题是如何分解为小问题的。

• 分治法

（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。
（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。

例如归并排序就是最常见的一种分治算法和思想。

• 贪婪法

（1）最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。
（2）贪心选择性质
所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。

设计思路：
（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。
（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。
（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。
（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。
（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

• 动态规划法

动态规划法与分治法类似，当问题不能分解为独立的子问题,但又符合最优化原理(最优子结构性质)时,用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。

• 回溯法

回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：
（1）用约束条件剪去得不到可行解的子树；
（2）用目标函数剪去得不到最优解的子树。
这两类函数统称为剪枝函数

四、 同一个问题，如TSP，01背包，不同策略的算法设计

TSP问题（旅行商问题）:Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

○动态规划:状态压缩DP,复杂度O(n²2ⁿ)。
○ 回溯法:穷举所有路径,复杂度O(n!)。

· 0-1背包问题:
○贪心法:按价值密度排序,可能非最优。
○动态规划:填表法,复杂度O(nW)。

具体代码在后续文章中实现。

五、 算法的分析方法，如排序算法的元素比较次数，递归方程。

归并排序
快速排序
堆排序
希尔排序

六、 适合贪婪法求解的问题，有什么特性？

（1）最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。
（2）贪心选择性质
所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。

问题具有最优子结构。

七、 随机算法的基本特征，分类，优缺点。

• 特征

执行过程中使用随机选择（如随机数生成）。

结果可能非确定，但概率可控。

• 分类：

蒙特卡罗算法：可能返回错误解，但速度快（如素数测试）。

拉斯维加斯算法：总能返回正确解，但时间不确定（如快速排序的随机化版本）。

• 优缺点：

优点：简单高效，适合并行。

缺点：结果可能不唯一，需多次运行验证。

八、 随机算法的典型应用，海量数据处理的一般方法。

• 典型应用：

随机抽样：大数据集的近似统计（如蓄水池抽样）。

加密算法：RSA中的随机数生成。

• 海量数据处理方法：

分治法：MapReduce框架（如Hadoop）。

布隆过滤器：高效查询是否存在某元素。

九、 什么是 P类、NP类、NPC类、NPH类问题。一般如何处理NPC类问题? 图灵机的基本模型。

归约：如果解决了问题A，就能用解决A的方法来解决问题B，那么我们说问题B可以归约为/到问题A，本文记为 [B]< [A]。 其含义就是问题A的求解复杂度比问题B要高.

P（Polynomial）类问题：多项式时间内可解的问题（如排序）。
NP类：多项式时间内可验证解的问题（如TSP）。
NPC类：NP中最难的问题，所有NP问题可归约到它（如SAT问题）。
NPH类：至少和NP问题一样难，所有NP问题可归约到它，但未必属于NP。

• 处理NPC问题：

近似算法：牺牲精度换取效率（如TSP的2-近似算法）。
启发式算法：如遗传算法、模拟退火。

图灵机模型：
由无限长纸带、读写头和状态寄存器组成，是理论计算模型的基础。