3.4 算法设计与复杂度分析
本篇定位：算法设计与复杂度分析是数据结构与算法的"方法论层"——回答"什么是好算法、如何度量算法效率"。9 年真题直接考过 2 题（2018 多80 好算法四目标、2019 多83 复杂度=时间+空间），且复杂度概念渗透所有章节（折半 O(log n)、排序 O(n log n)）。2027 预测明确把复杂度列为数据结构板块补考点。本章把算法特征、评价目标、大 O 复杂度、常见设计策略讲透。 数据依据：
01-真题/真题文本/+01-真题/考点汇总/；答案以专业判断为准。 阅读提示：复杂度是 3.1/3.2/3.3 各章的"横切面"；设计策略（分治/贪心/动态规划）与第 8 篇金融科技（机器学习算法）概念互通。
一、考点定位（本章真题统计）
| 考点 | 真题锚点 | 频次 | 考法 |
|---|---|---|---|
| 好算法的评价目标 | 2018 多80 | 1 年 | 正确性、可读性、健壮性、高效性（全选） |
| 算法复杂度构成 | 2019 多83 | 1 年 | 复杂度 = 时间复杂度 + 空间复杂度 |
| 复杂度计算 | — | 0 年 | 未直接考（渗透在折半/排序题中） |
| 算法设计策略 | — | 0 年 | 未考（防漏网） |
命题规律：算法基础概念两年各 1 题（2018 多80、2019 多83），全部是概念多选题；复杂度计算题未单独出现（2024 单28 折半次数本质就是复杂度计算）。2027 预测：复杂度（低位，且逐年压缩）——预计 0–1 题，以"时间/空间复杂度判定"或"大 O 阶排序"形式出现。核心能力：认识大 O 符号、能排复杂度阶、记住算法特征五条与评价四目标。
二、知识框架（先搭骨架）
算法（Algorithm）= 解决特定问题的有限指令序列
├── 五个特征（必背）
│ ├── 有穷性：有限步骤内结束（不死循环）
│ ├── 确定性：每条指令含义明确、无二义
│ ├── 可行性：每条指令都能执行
│ ├── 输入：0 个或多个
│ └── 输出：1 个或多个
├── 好算法的四个评价目标（2018 多80，全选）
│ ├── 正确性、可读性、健壮性（容错）、高效性（时间空间省）
├── 算法效率度量
│ ├── 时间复杂度：基本操作执行次数随规模 n 的增长函数（大 O）
│ ├── 空间复杂度：运行所需内存随规模 n 的增长函数
│ └── 大 O 阶（从小到大）：
│ O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
├── 常用算法设计策略
│ ├── 分治法：分解→解决→合并（折半查找、归并、快排）
│ ├── 贪心法：每步选当前最优（Dijkstra、Prim/Kruskal、哈夫曼）
│ ├── 动态规划：重叠子问题 + 最优子结构，备忘录（Floyd、背包、LCS）
│ ├── 回溯法：试探 + 回退（八皇后、迷宫、N 皇后）
│ ├── 递归：函数调用自身（阶乘、斐波那契、树的遍历）
│ └── 枚举/暴力：穷举所有可能
└── 算法分析常识
├── 递归实现 → 系统栈（空间 O(递归深度)）
├── 二分/分治 → O(log n) 或 O(n log n)
└── 双层循环 → O(n²)
一句话记忆：算法五特征（有穷确定可行，输入输出）、好算法四目标（正确可读健壮高效）、复杂度两维度（时间+空间）、大 O 七阶排序、设计六策略（分治贪心动态回溯递归枚举）。
三、考点详解
3.1 算法的定义与五个特征
精确定义：算法 = 对特定问题求解步骤的描述，是指令的有限序列。
五个特征（2018 多80 的题干基础）：
- 有穷性：算法必须在有限步骤内结束（不能死循环）——程序可以无限运行（操作系统），但算法必须有限；
- 确定性：每条指令含义明确、无二义性，相同输入必有相同输出；
- 可行性：每条指令都能实际执行（用基本运算实现）；
- 输入：0 个或多个（可以没有输入）；
- 输出：1 个或多个（必须有输出，否则无意义）。
坑："算法必须要有输入"是错误说法（输入可以是 0 个）；"算法的每一步都可以有歧义"错误（必须确定）。
3.2 好算法的四个评价目标（2018 多80，全选）
2018 多80 真题：一个"好"的算法应考虑多个目标，包括（口径已核）。 A. 正确性 B. 可读性 C. 健壮性 D. 高效性 → 答案：ABCD（全选）
精确定义：
- 正确性：算法能正确解决问题（结果正确）；
- 可读性：算法便于阅读、理解、修改（好的算法可读性好——教学常强调）；
- 健壮性：对非法输入能合理处理（容错，不崩溃、不产生错误结果）；
- 高效性：时间（运行快）和空间（占用内存少）效率高。
注意"健壮性"≠"正确性"：正确性是"输入合法时结果对"，健壮性是"输入非法时不死机、能给出合理提示"。
3.3 时间复杂度与空间复杂度（2019 多83）
2019 多83 真题：算法复杂度一般包括（口径已核）。 A. 系统复杂度 B. 时间复杂度 C. 计算复杂度 D. 空间复杂度 → 答案：BD
精确定义：
- 时间复杂度：算法执行基本操作（如比较、赋值）的次数随问题规模 n 增长的数量级，用大 O 记号表示（忽略常数系数和低阶项）；
- 空间复杂度：算法运行所需的辅助存储空间随 n 增长的数量级。
大 O 阶（从小到大，必背）：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
常数 对数 线性 线性对数 平方 指数 阶乘
常见算法复杂度速查：
| 复杂度 | 代表算法 |
|---|---|
| O(1) | 数组随机存取、哈希查找（平均）、栈/队列操作 |
| O(log n) | 折半查找（2019 单59、2024 单28） |
| O(n) | 顺序查找、链表遍历、单链表查找 |
| O(n log n) | 快排（平均）、堆排序、归并排序 |
| O(n²) | 冒泡/选择/插入排序（平均）、双重循环、Dijkstra（邻接矩阵实现） |
| O(n³) | Floyd 算法（三重循环：任取中间点 k × 起点 i × 终点 j） |
| O(2^n) | 斐波那契（朴素递归）、子集枚举 |
复杂度计算三原则：
- 单层循环 n 次 → O(n)；嵌套两层 → O(n²)；
- 每次规模减半（二分）→ O(log n)；
- 循环内调用 O(m) 的子过程 → O(n×m)（如排序里套查找）。
3.4 常用算法设计策略（防漏网重点）
精确定义与示例：
- 分治法：把大问题分解成若干相同类型的子问题，分别解决后合并结果——折半查找、归并排序、快速排序；
- 贪心法：每一步都做当前最优选择，不回溯——Dijkstra 最短路径、Prim/Kruskal 最小生成树、哈夫曼编码、活动安排；
- 动态规划：把问题分解成重叠子问题，保存子问题解避免重复计算（备忘录）——Floyd 最短路径、0/1 背包、最长公共子序列（LCS）；
- 回溯法：试探 + 回退，走不通就退回去换路——八皇后、迷宫求解、N 皇后；
- 递归：函数直接或间接调用自身——阶乘、斐波那契、树的遍历；
- 枚举法：穷举所有候选解，逐一检验——暴力查找（适合规模小）。
辨析要点：
- 分治 vs 动态规划：分治的子问题相互独立（归并），动态规划的子问题重叠（背包）；
- 贪心 vs 动态规划：贪心不回退（局部最优未必全局最优），动态规划全面比较（保证全局最优）；
- 递归的空间代价：递归深度决定空间复杂度（如朴素递归斐波那契深度 n → 空间 O(n)）。
四、易错坑汇总（命题人惯用陷阱）
- "算法必须要有输入"是错误说法——算法特征五条：输入 0 个或多个（可以不输入）。
- "算法必须输出"是正确说法——输出 1 个或多个（没有输出的算法无意义）。
- 复杂度 = 时间 + 空间（2019 多83）——"系统复杂度""计算复杂度"是干扰项；"计算复杂度"不是算法复杂度的标准分类。
- 好算法四目标全选（2018 多80）——正确性、可读性、健壮性、高效性四个都要；单选"只要高效"是错误说法。
- 健壮性 vs 正确性——健壮性是"非法输入不崩溃"（容错），正确性是"合法输入结果对"；两者不同维度。
- 大 O 只关心数量级——忽略常数与低阶项：O(3n+5) 就是 O(n)；"O(2n) 比 O(n) 慢一倍"是错误说法（同一阶）。
- 折半查找 O(log n)、顺序查找 O(n)——复杂度与查找方法绑定，别混。
- 快排平均 O(n log n)、最坏 O(n²)——"快排任何情况都是 O(n log n)"是错误说法（见 3.3 章）。
- 递归的空间复杂度——递归用系统栈，空间 O(递归深度)；"递归空间 O(1)"是错误说法。
五、横向扩展（防漏网：本章边界内、真题尚未考但可能补考的点）
说明：横向扩展覆盖"大纲范围内但 9 年真题未考过"的知识，标注【新增概率】供取舍。
- 复杂度阶排序【高】：O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2^n)——"下列复杂度由小到大排列"类题高概率。
- 具体代码复杂度计算【中】：给一段双层循环/二分循环代码求大 O——基础课常见题。
- 递归 vs 迭代【中】：递归（函数自调用、栈开销）vs 迭代（循环）——"递归一定比迭代高效"是错误说法（通常更慢）。
- 分治/贪心/动态规划匹配【中】：给算法名问设计策略（折半=分治、Dijkstra=贪心、Floyd=动态规划）——匹配题。
- NP 问题概念【低】：P（多项式时间可解）、NP（多项式时间可验证）、NP 完全——只需知道"P⊆NP、是否 P=NP 未解决"。
- 贪心不一定全局最优【中】："贪心算法一定能得到全局最优解"是错误说法（局部最优≠全局最优，除非问题有贪心选择性质）。
- 算法的确定性 vs 程序【低】：算法必须有穷性；程序（如操作系统）可以无限运行——"程序就是算法"是错误说法（程序可以不满足有穷性）。
- 随机化/近似算法【低】：随机化算法（快排随机基准）、近似算法（NP 难题）——名词辨析。
六、真题演练（代表性真题 + 解析）
例 1（2018 多80） 通常一个"好"的算法应考虑多个目标，包括（口径已核）。 A. 正确性 B. 可读性 C. 健壮性 D. 高效性
答案：ABCD（全选）。好算法的四目标：正确性（结果对）、可读性（易读易改）、健壮性（非法输入不崩溃）、高效性（时间空间省）。口诀：正确可读健壮高效，四个都要。
例 2（2019 多83） 算法复杂度一般包括（口径已核）。 A. 系统复杂度 B. 时间复杂度 C. 计算复杂度 D. 空间复杂度
答案：BD。算法复杂度 = 时间复杂度（运行时间随规模的增长）+ 空间复杂度（内存占用随规模的增长）。"系统复杂度""计算复杂度"是干扰项。口诀：复杂度就俩——时间和空间。
例 3（防漏网·复杂度计算） 一个算法的时间复杂度为 O(log₂n)，当 n=8 时执行 3 次基本操作；当 n=64 时，大约执行（口径已核）次。 A. 4 B. 6 C. 8 D. 12
答案：B。O(log₂n)：log₂64 = 6 次（log₂8=3、log₂64=6，规模扩大 8 倍只多 3 次——对数复杂度的特点：增长极慢）。口诀：log n 涨得慢，翻倍只加 1。
例 4（防漏网·设计策略） 下列算法中，采用"分治"策略的是（口径已核）。 A. 折半查找 B. 冒泡排序 C. 直接插入排序 D. 简单选择排序
答案：A。折半查找把搜索区间不断对半分解——典型分治（也有递归实现）；冒泡/插入/选择都是"比较交换"类，不用分治。口诀：折半、归并、快排=分治。
例 5（防漏网·特征辨析） 下列关于算法的叙述，错误的是（口径已核）。 A. 算法必须有输入 B. 算法必须在有限步骤内结束 C. 算法的每一步必须明确无二义 D. 算法必须有输出
答案：A。算法特征：输入 0 个或多个（可以没有输入）、输出 1 个或多个、有穷性（有限步骤）、确定性（无二义）、可行性。A 说"必须有输入"错误。口诀：输入可为零，输出必须有。
七、本章小结
- 一条主线：算法定义与五特征（有穷/确定/可行/输入/输出）→ 好算法四目标（正确/可读/健壮/高效）→ 复杂度两维度（时间+空间、大 O 七阶）→ 设计六策略（分治/贪心/动态规划/回溯/递归/枚举）。
- 必背概念：2018 多80 四目标全选；2019 多83 复杂度=时间+空间；算法"必须有输入"是错误说法。
- 必背复杂度：O(1)<O(log n)<O(n)<O(n log n)<O(n²)<O(2^n)；折半 O(log n)、快排平均 O(n log n)/最坏 O(n²)、冒泡选择插入 O(n²)。
- 必背对应：折半/归并/快排=分治；Dijkstra/Prim/Kruskal/哈夫曼=贪心；Floyd/背包/LCS=动态规划；八皇后/迷宫=回溯。
- 衔接预告：复杂度贯穿 3.1–3.3 各章；贪心/动态规划与第 8 篇金融科技（机器学习、路径优化）衔接；哈希/索引与第 4 篇数据库衔接。