calculate19｜第2-7章算法时间空间复杂度分步解题

ONEPSOFT | 软考学习知识库

---

calculate19｜第2-7章算法时间空间复杂度分步解题

配套动画：calculate40｜第 2-7 章算法时间空间复杂度解题动画.html

说明：大 O 严格定义与主定理属标准计算机科学方法（教程第 7 章以具体算法 O(…) 实例呈现，未逐字给理论定义），本文件依标准 CS 方法构造并标注。

一、题目

题目 A（嵌套循环）：下列代码的时间复杂度？

for i = 1..n {
    for j = 1..n {
        基本操作
    }
}

题目 B（主定理）：递归式 T(n) = 2T(n/2) + O(n) 的时间复杂度？

二、核心公式（先算准）

• 大 O 记号：若存在正常数 c、n0，使 n≥n0 时 0≤f(n)≤c·g(n)，则 f(n)=O(g(n))（渐进上界，丢常数/低阶/系数）。
• 常见阶数（由快到慢）：O(1) \< O(log n) \< O(n) \< O(n log n) \< O(n²) \< O(n³) \< O(2ⁿ) \< O(n!)。
• 嵌套循环：时间复杂度 = 各层阶数相乘（层乘阶）。
• 主定理：对 T(n)=aT(n/b)+f(n)（a≥1, b>1），先算关键量 n^(log\_b a)，再与 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))

三、分步计算

题目 A：嵌套循环判阶

• 外层 i 循环执行 n 次；
• 每次内层 j 循环执行 n 次；
• 基本操作总次数 = n × n = n²；
• 故 T(n) = O(n²)。

口诀 " 层乘阶 "：两层同阶循环 → 阶数相乘。三层 → O(n³)；一层 → O(n)。

题目 B：主定理

1. 识别参数：a=2, b=2, f(n)=O(n)。
2. 算关键量：log\_b a = log\_2 2 = 1 → n^(log\_b a) = n¹ = n。
3. 比较 f(n)=O(n) 与 n：二者同阶，属情形 2。
4. 情形 2 公式：T(n) = Θ(n^(log\_b a) · log n) = Θ(n · log n) = O(n log n)。

这正是归并排序、快速排序平均情况的标准复杂度，优于朴素 O(n²)。

空间复杂度

• 时间复杂度看 " 操作次数趋势 "，空间复杂度看 " 额外内存随 n 的趋势 "。
• 题目 A 只用了常数个变量 → 空间 O(1)；若另开 n×n 二维数组则为 O(n²)。
• 题目 B 递归栈深度约 log n（或自底向上 O(1)）→ 典型 O(log n)\~O(n)。

四、结果汇总

题目	类型	时间复杂度	空间 (典型)
A	双层循环	O(n²)	O(1)
B	主定理情形 2	O(n log n)	O(log n)\~O(n)

五、考试要点与易错

1. 层乘阶：嵌套循环阶数相乘，勿把 O(n²) 误判成 O(2n)。
2. 主定理先算 log\_b a：a=2,b=2→log\_2 2=1；a=3,b=2→log\_2 3≈1.585。
3. 情形判定看 " 谁大 "：f(n) 比 n^log 小→情形 1；同阶→情形 2；大且正则→情形 3。
4. log 底省略：复杂度里 log n 默认以 2 为底，写 O(log n)/O(n log n) 均可。
5. 时间≠空间：二者常需权衡（空间换时间），选择题会分别考。