第一章：算法的概念及复杂性度量（复习笔记）

一、基础概念 (Definitions)

1. 算法 vs 程序

• 算法 (Algorithm)：解决问题的逻辑蓝图。必须满足五大特征：
  1. 有限性（必须终止）
     
  2. 确定性（无歧义）
     
  3. 输入（0个或多个）
     
  4. 输出（至少1个）
     
  5. 有效性（每一步都可执行）
• 程序 (Program)：算法用编程语言的具体实现。程序可以不终止（如操作系统），侧重实现细节。

2. 渐近符号体系 (Asymptotic Notations)

用于描述当输入规模 时，算法效率的增长趋势。

符号	含义	数学定义（存在正常数 ，对 ）	直观理解
	渐近上界（最坏情况）		算法最坏不会超过这个级别
	渐近下界（最好情况）		算法最快不会低于这个级别
	紧确界（平均情况）		算法的增长速率精确为这个级别
	非紧上界	对任意 ，存在 使得	增长严格慢于
	非紧下界	对任意 ，存在 使得	增长严格快于

---

二、复杂性证明方法 (Proof Methods)

核心方法：放缩法寻找 和

要证明 或 ，核心是构造不等式，找到满足条件的常数 和起始点 。

例题1：证明上界

题目：证明

证明：
1. 目标：找 ，使得
2. 放缩：当 时，

3. 结论：取 ，证得

例题2：证明下界

题目：证明

证明：
1. 目标：找 ，使得
2. 放缩：当 时，；同时

3. 匹配系数：令
4. 结论：取

证得

例题3：小o符号的理解

题目：证明

理解：
- 对于任意 （如 ），只要 足够大（），都有
- 这体现了 的增长速度严格慢于
—

三、递归方程求解方法 (Solving Recurrences)

这是计算题的核心，针对不同类型的方程使用不同方法。

方法1：主定理 (Master Theorem) - 参数k版本

适用：分治算法形式

参数说明：
- ：子问题个数
- ：规模缩小倍数
- ：合并步骤的时间复杂度指数（即非递归部分为 ）

比较 与 的大小关系：

情况	判别条件	时间复杂度	直观理解
情况1			递归代价主导（叶子节点多）
情况2			各层代价均衡（需乘 ）
情况3			合并代价主导（根节点代价高）

记忆口诀：
- ：叶子说了算 →
- ：平起平坐 →
- ：根说了算 →

例题

求解

1. 参数识别：（因为 ）
   
2. 计算比较：
   
3. 判断大小：，符合情况1
   
4. 结论：

---

方法2：特征方程法 (Characteristic Equation)

适用：线性常系数齐次递归方程

步骤：
1. 写出特征方程（）
2. 求特征根
3. 写出通解：
- 若 ：
- 若 ：
4. 代入初始条件解出

例题

求解 ，

1. 移项：
   
2. 特征方程：
   
3. 特征根：
   
4. 通解：
   
5. 代入初值：
   • ：
     
   • ：
     
   • 解得：
     
6. 最终解：

特别注意

如果特征根是重根，那么需要转变为：
，代入初始值解出c1,c2

---

方法3：迭代法 (Iteration Method)

适用：无法用主定理的方程，如

步骤：逐层展开，直到找出求和规律

例题

求解 ，

1. 展开：
   
   
   
   
2. 规律：
   
3. 求和：等差数列求和
   
4. 解：

---

四、经典案例：最大子段和问题

展示算法优化如何显著改变效率

• 问题：给定序列，求和最大的连续子序列
  
• 演变路径：
  1. 暴力法：三层循环，枚举所有起点终点并求和 →
     
  2. 前缀和优化：两层循环，去除重复计算 →
     
  3. 分治法：递归将数组一分为二，处理跨中点情况 →
     
  4. 动态规划（在线处理）：一遍扫描，累加和小于0则丢弃 →

---

五、复习要点总结

1. 必须掌握的定义

• 算法的五大特征
  
• 渐近符号 的数学定义和直观理解

2. 关键证明技巧

• 放缩法构造 和
  
• 反证法证明最优子结构

3. 递归方程求解能力

• 主定理：快速判断分治算法复杂度
  
• 特征方程法：必考计算题，掌握二阶线性常系数递归
  
• 迭代法：简单递归方程的展开求和

4. 算法优化思维

• 从暴力法 到最优解 的演变过程
  
• 理解不同算法设计思想（分治、动态规划）的适用场景

---

本章核心：建立算法分析的基本框架，掌握复杂度证明和计算的核心方法，为后续章节的学习奠定坚实基础。