算法设计与分析：期中复习导引与核心知识主线

本篇系统梳理算法设计与分析课程前四章的核心知识脉络，涵盖计算模型与复杂度分析、递归分治策略、动态规划设计以及贪心算法及其正确性证明。期中考查重点聚焦于：基本概念辨析、时间/空间复杂度推导、算法建模与伪代码描述、以及算法正确性的严格证明。

---

一、知识体系结构与学习路径

算法设计与分析的考核不仅关注算法的实现细节，更侧重于分析算法在任意合法输入下的正确性保证与资源消耗上界。前四章的核心知识模块划分如下：

学习次序	知识模块	核心理论与推导重点	掌握要求与考核形式
1	计算复杂度与理论基础	渐近记号（$O, \Omega, \Theta$）、循环级数求和、主定理、最好/最坏/平均情况、P/NP/NPC 理论与归约	概念辨析题、级数求和手算、归约方向与问题分类判定
2	递归分治策略	二分查找不变量、归并排序与逆序对、快速选择（期望线性时间）、Karatsuba/Strassen 降维分治、棋盘覆盖与最近点对	算法伪代码、分治递推方程求解、几何与构造性分治证明
3	动态规划设计	最优子结构、无后效性、最后一步决策推演、0-1 背包（倒序循环原理）、LCS、最大子段和、区间 DP、六大经典实验题	状态严密定义、状态转移方程推导、填表拓扑与空间优化
4	贪心算法与证明	贪心选择性质、交换论证法（Exchange Argument）、活动安排、分数背包、哈夫曼树、Dijkstra（非负权先决条件）、Prim/Kruskal	贪心策略设计、交换论证法规范证明、反例构造辨析
5	期中典型题与模拟试卷	教材代表性习题详解与一套 100 分全真模拟试卷	综合建模、规范化解答六步法演练

---

二、四大算法设计范式的决策本质对比

面对一个规模为 $n$ 的离散优化或判定问题，不同算法范式在解空间的探索方式上存在本质差异：

flowchart TD
    Problem["优化/判定问题求解"] --> Strategy{"解空间决策拓扑"}
    Strategy -->|"子问题相互独立<br>无重叠计算"| Divide["分治法 (Divide and Conquer)<br>递归划分子问题，双指针或代数合并"]
    Strategy -->|"子问题大量重叠<br>具备无后效性"| DP["动态规划 (Dynamic Programming)<br>枚举最后决策，表格记录历史局部解"]
    Strategy -->|"具备贪心选择性质<br>局部最优即全局最优"| Greedy["贪心算法 (Greedy Algorithm)<br>依准则单向推进，无需枚举所有分支"]

比较维度	分治法（Divide and Conquer）	动态规划（Dynamic Programming）	贪心算法（Greedy Algorithm）
子问题依赖关系	子问题之间严格相互独立，互不重叠	子问题之间存在大量重叠子结构	做出贪心选择后，仅产生一个剩余子问题
计算与存储方式	自顶向下递归求解，一般仅需递归栈空间	自底向上（或带备忘录自顶向下）填表，需显式开辟数组保存中间状态	自顶向下单向迭代或堆优化贪心选取，辅助空间通常较小
决策时机与范围	不涉及状态优选，按几何或代数结构机械切分	在每个状态处完备枚举所有候选决策并取极值（$\max/\min$）	在每一步依据局部启发式准则直接确定最优分支，不回溯
正确性证明工具	数学归纳法证明递归基与归纳步	证明最优子结构与状态转移覆盖的完备性	交换论证法（Exchange Argument）证明贪心选择包含在全局最优解中

---

三、算法设计大题的规范解答流程

在期中考试的算法设计大题中，建议采用严密规范的六步表述结构，以保证答题逻辑完整：

1. 问题建模与形式化描述：
   • 用准确的数学符号定义输入集合、约束条件与优化目标函数（如最小化耗时或最大化收益）。
2. 状态或策略定义：
   • 动态规划：明确说明状态数组（如 $dp[i][j]$）的每一个下标所代表的物理含义（如前缀、区间、资源容量约束）；
   • 贪心算法：明确给出元素排序或选取的贪心准则（如按结束时间升序排列）。
3. 状态转移方程或核心算法逻辑：
   • 动态规划：列出完整的分类转移方程，标明各分支的取值条件；
   • 贪心/分治：给出结构严谨的高层次伪代码。
4. 算法正确性证明：
   • 贪心题必须严格书写交换论证法：假设存在最优解未包含贪心选择，通过元素替换构造新解，并证明新解依然合法且目标函数值不劣于原最优解；
   • 分治与动态规划阐明最优子结构成立的代数依据。
5. 计算复杂度与存储空间分析：
   • 显式给出状态总数与每个状态的转移代价，推导出紧确界 $\Theta(f(n))$；说明额外开辟的辅助数组或递归栈深度。
6. 边界条件与特判：
   • 说明空输入、单元素、极值（如全负数、容量为 0）以及递归基的初始化赋值。

---

四、核心概念自查要点

在进入各章节深研前，可通过以下核心问题进行自检：

1. 复杂度分析：为什么 0-1 背包的动态规划解法时间复杂度为 $O(nC)$，却被定义为伪多项式时间？（提示：输入规模应以二进制比特长度度量，数值 $C$ 相对于其比特长度呈指数增长）。
2. 分治合并代价：二分查找每次将问题规模减半，为什么总时间是 $\Theta(\log n)$ 而不是 $\Theta(n)$？（提示：二分查找在每层仅做常数级比较，不存在线性合并过程）。
3. 状态无后效性：在最大连续子段和问题中，为什么不能将状态定义为“前 $i$ 个数中的全局最大子段和”？（提示：该定义无法确定子段是否与第 $i$ 个元素相连，无法无后效地向右延伸）。
4. 贪心选择证明：在活动安排问题中，为什么必须选择结束时间最早的活动，而选择持续时间最短的活动可能得到次优解？（提示：尽早释放资源为后续决策保留最大可行时间域；持续时间短的活动可能切断两个更高效的相容活动）。