speedrun23｜第2-7章算法时间空间复杂度速通

ONEPSOFT | 软考学习知识库

---

speedrun23｜第2-7章算法时间空间复杂度速通

用 " 工期估算/用料估算 " 类比。复杂度就是 " 规模变大时，耗时/占内存怎么涨 "。本速通配合同条 calculate40 动画练计算。

一、章节定位

一句话概括：本章讲 " 怎么用大 O 记号刻画算法随数据规模 n 增长的耗时 (时间复杂度) 和占内存 (空间复杂度)"，以及主定理算递归复杂度。

• 题型覆盖：综合知识【✓✓】 ｜ 案例分析【✓】 ｜ 论文【○】
• 重要性等级：【★★★★】——大 O 阶数排序、嵌套循环阶数、主定理三情形是选择题计算题常客
• 教材出处：第 7 章算法相关 + 第 2 章数学基础（注：教程片段以具体算法 O(…) 实例呈现，大 O 严格定义与主定理按标准 CS 方法构造，标注于 calculate40）

二、本章在讲什么（系统性阐述）

复杂度分析像估算 " 工程量随楼高怎么变 "：

• 时间复杂度 T(n)：算法运行时间随输入规模 n 的增长趋势，用大 O 记号表示渐进上界，忽略常数与低阶项。
• 空间复杂度 S(n)：算法额外占用内存随 n 的增长趋势。
• 常见阶数（由快到慢）：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。
• 嵌套循环：外层×内层，如 for i..n { for j..n { } } → O(n²)。
• 主定理 (Master Theorem)：对递归式 T(n)=aT(n/b)+f(n) 直接判阶：
• 情形 1：f(n)=O(n^(log_b a − ε)) → T(n)=Θ(n^(log_b a))
• 情形 2：f(n)=Θ(n^(log_b a)) → T(n)=Θ(n^(log_b a) log n)
• 情形 3：f(n)=Ω(n^(log_b a + ε)) 且正则 → T(n)=Θ(f(n))

三、教材原文精摘（教程实例 + 标准 CS 补充，已标注）

教程实例（第 7 章算法）原文摘录：普里姆算法时间复杂度为 O(n²)（与图中边数无关）；克鲁斯卡尔算法 O(e log₂e)（与顶点数无关）；贝尔曼 - 福特算法 O(nm)（n 节点 m 边，可检测负权回路）；A\* 算法时间复杂度通常为 O(b^d)（b 分支因子，d 最短距离）。

教程约定（归纳）：教程对所有算法均以 "O(…)" 记法表达渐进复杂度，以输入规模（n 顶点、e/m 边、V/E 节点边、b/d 树参）为复杂度变量。

大 O 严格定义（标准 CS，教程未直接给，依标准方法构造）：若存在正常数 c 和 n₀，使对所有 n≥n₀ 有 0≤f(n)≤c·g(n)，则称 f(n)=O(g(n))，即 g(n) 是 f(n) 的渐进上界。

主定理（标准 CS，教程未直接给）：对 T(n)=aT(n/b)+f(n)（a≥1,b>1 常数）：比较 f(n) 与 n^(log_b a) 三情形定阶（见上 " 本章在讲什么 "）。

逐段讲解：

• 针对教程实例：这是大 O 的应用示范——不同算法不同阶，普里姆 O(n²)、克鲁斯卡尔 O(e log e) 等。
• 针对教程约定：教程统一用 O(…) 且以输入规模作变量，说明复杂度分析是 " 看规模趋势 "。
• 针对大 O 定义：本质 " 被某个简单函数 c·g(n) 从上方包住 "，所以常数、低阶、系数都扔掉。
• 针对主定理：递归算法 (分治) 专用速算表，三情形看 f(n) 与 n^(log_b a) 谁大谁小。

四、核心知识树

算法复杂度

├── 大 O 记号
│ └── 渐进上界 (丢常数低阶)
├── 常见阶数
│ └── 1\├── 嵌套循环
│ └── 层阶相乘
└── 主定理
└── T(n)=aT(n/b)+f(n) 三情形

五、知识脑图总结

思维导图（结构化呈现）

• 算法复杂度
  • 大O
    • 渐进上界
  • 阶数
    • 1 log n n nlogn n2 2n
  • 嵌套循环
    • 相乘
  • 主定理
    • 三情形

六、关键概念速解

概念	定义（标准/CS）	大白话速解	考试怎么考
时间复杂度	运行时间随 n 趋势	耗时怎么涨	选择/计算：判阶
空间复杂度	额外内存随 n 趋势	占内存怎么涨	选择：与时间的区分
O(1)	常数阶	与规模无关	选择：阶数排序
O(n²)	平方阶	双层循环	选择：嵌套循环
O(2ⁿ)	指数阶	爆炸增长	选择：最慢阶
主定理	递归三情形	分治速算表	计算：归并/快排阶

七、记忆口诀 & 类比

• 口诀：「1 对 l n nln n 方 2n」→ 阶数由快到慢：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。
• 口诀：「层乘阶」→ 嵌套循环时间复杂度 = 各层阶相乘（两层 n 循环→n²）。
• 类比：时间复杂度像工期随楼层 n 的变化——O(1) 是 " 不管几层都一天 "(常数)、O(n) 是 " 每层一天 "、O(n²) 是 " 每层都要和前面每层对账 "(双层嵌套)、O(2ⁿ) 是 " 每加一层工序翻倍爆炸 "。主定理像 " 分包施工 (分治) 的标准工期公式 "。

八、易混淆点对比

易混项 A	易混项 B	核心区别
时间复杂度	空间复杂度	时间=耗时趋势；空间=内存趋势
O(n)	O(n²)	单层循环 vs 双层嵌套循环
O(n log n)	O(n²)	分治排序 (快/归并) vs 朴素双重循环
主定理情形 1	情形 3	情形 1 叶子主导 (n^log); 情形 3 根主导 (f(n))

九、与其他章节的关联

• 上游/前置：第 2 章数学基础（对数、级数）、递归思想。
• 下游/依赖：第 7 章具体算法（普里姆/克鲁斯卡尔/Bellman-Ford 等复杂度）、案例性能分析。
• 联动考点：复杂度与第 12 章质量属性 " 性能 "、第 14 章 McCabe 圈复杂度 (不同概念，注意区分) 呼应。
• 联动考点：复杂度本身是 " 分析 " 不是 " 运维 "，但理解 O(n²) 会爆，能帮你在运维/架构章判断 " 哪种实现会拖垮性能 "——性能问题本质是复杂度问题。

十、考试出题方式

• 选择题：给代码片段判时间复杂度 (尤其嵌套循环)；阶数大小排序；主定理判递归阶 (如 T(n)=2T(n/2)+O(n)→O(n log n))。
• 案例分析：给算法改法问复杂度是否优化。
• 论文：一般不单独考，可作性能论证。

说明：大 O 严格定义与主定理教材片段未逐字收录，本条依标准计算机科学方法构造并明确标注，未伪称教程原文；实例均引自教程第 7 章。