模块 05 · 高分分水岭
代码追踪与复杂度分析
在非上机编程的纸笔/机考测试中,纯手工阅读 C++ 代码并准确推导其变量流向与渐进复杂度,是区分“代码打字员”与“真正算法选手”的关键分水岭。
5.2 手工代码追踪与位运算自反性
面对复杂的循环和判断,不要试图在脑中凭空“脑补”,而应在草稿纸上建立严谨的变量追踪表格。
真题直击 · 2025 第17题
位运算异或(XOR)自反性与无变量交换
分析以下神奇的 C++ 函数:
int calc(int x, int y) {
x = x ^ y;
y = x ^ y;
x = x ^ y;
return x;
}
异或核心性质:
1. 归零律:
2. 恒等律:
3. 交换律与结合律:顺序可任意调整。
推导演变:
• 第 1 步:x 变为
• 第 2 步:y = x ^ y = (x₀ ^ y₀) ^ y₀ = x₀ ^ (y₀ ^ y₀) = x₀ ^ 0 = x₀(y 成功获得了原始的 x!);
• 第 3 步:x = x ^ y = (x₀ ^ y₀) ^ x₀ = (x₀ ^ x₀) ^ y₀ = 0 ^ y₀ = y₀(x 成功获得了原始的 y!);
• 最终返回 x,即返回原始的 y!
1. 归零律:
a ^ a = 0;2. 恒等律:
a ^ 0 = a;3. 交换律与结合律:顺序可任意调整。
推导演变:
• 第 1 步:x 变为
x₀ ^ y₀;• 第 2 步:y = x ^ y = (x₀ ^ y₀) ^ y₀ = x₀ ^ (y₀ ^ y₀) = x₀ ^ 0 = x₀(y 成功获得了原始的 x!);
• 第 3 步:x = x ^ y = (x₀ ^ y₀) ^ x₀ = (x₀ ^ x₀) ^ y₀ = 0 ^ y₀ = y₀(x 成功获得了原始的 y!);
• 最终返回 x,即返回原始的 y!
条件分支与变量累加跟踪表示范
追踪以下循环片段的输出结果:
int s = 0, i = 1;
while (i <= 5) {
if (i % 2 == 1) s += i * 2;
else s += i;
i++;
}
| 循环轮次 | 当前 i | 奇偶判断 | s 增量 | 最新 s |
|---|---|---|---|---|
| 1 | 1 | 奇数 | + 1 × 2 = 2 | 2 |
| 2 | 2 | 偶数 | + 2 | 4 |
| 3 | 3 | 奇数 | + 3 × 2 = 6 | 10 |
| 4 | 4 | 偶数 | + 4 | 14 |
| 5 | 5 | 奇数 | + 5 × 2 = 10 | 24 |
5.3 大 O 渐进复杂度阶层与双重循环真题
大 O 符号描述的是当输入规模 n 趋向无限大时,算法计算操作次数增长的渐进上界。在计算大 O 时,遵循两个原则:
1. 只保留最高阶项(低阶项在大规模时微不足道);
2. 省略最高阶项的常数系数(如 5n² 简记为 O(n²))。
📈 算法复杂度增长速度梯队排行(从优秀到灾难)
O(1) 常数阶 <
O(log n) 对数阶 <
O(n) 线性阶 <
O(n log n) 线性对数阶 <
O(n²) 平方阶 <
O(2ⁿ) 指数阶 <
O(n!) 阶乘阶
真题直击 · 2025 第19题
内层翻倍循环的时间复杂度分析
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j *= 2) {
sum += a[i];
}
}
外层循环分析
变量 i 从 1 到 n,每次自增 1,共执行 n 次。
内层循环分析
变量 j 从 1 开始,每次乘以 2:
循环终止条件为 2ᵏ > n,即 k = log₂ n。
因此内层循环的实际执行次数为 log₂ n 次(以 2 为底的对数阶)。
j = 1, 2, 4, 8, 16, ..., 2ᵏ。循环终止条件为 2ᵏ > n,即 k = log₂ n。
因此内层循环的实际执行次数为 log₂ n 次(以 2 为底的对数阶)。
综合结论
外层循环每执行一次,内层循环独立执行 log n 次。总执行次数 = n · log₂ n。
因此整体时间复杂度为 O(n log n)(对应选项 B)。
因此整体时间复杂度为 O(n log n)(对应选项 B)。
5.4 递归调用树与组合数递归复杂度
评估没有记忆化数组的递归函数时,最直观的方法是画出其递归树(Recursion Tree)并统计叶子节点总数。
真题直击 · 2025 第20题 绝妙解法
递归计算组合数 C(n, m) 的时间复杂度
int C(int n, int m) {
if (m == 0 || m == n) return 1;
return C(n - 1, m) + C(n - 1, m - 1);
}
核心洞察:从返回值反推递归叶子总数!
• 观察函数体:所有的实质运算,都是到达递归基时返回一个数字 1;
• 中间所有非叶子节点,仅仅做了一件事:把左子树和右子树返回的数字相加(
• 换句话说,最终函数返回的庞大组合数数值 C(n, m),全都是由所有的递归基叶子节点“+ 1”累加而成的!
• 这意味着:整棵递归树的叶子节点个数,恰好不多不少正好等于组合数的数值 C(n, m)!
• 二叉树的总节点数与叶子数同阶。因此该递归函数的时间复杂度严格为 O(C(n, m))(对应选项 C)!
• 观察函数体:所有的实质运算,都是到达递归基时返回一个数字 1;
• 中间所有非叶子节点,仅仅做了一件事:把左子树和右子树返回的数字相加(
return C(...) + C(...));• 换句话说,最终函数返回的庞大组合数数值 C(n, m),全都是由所有的递归基叶子节点“+ 1”累加而成的!
• 这意味着:整棵递归树的叶子节点个数,恰好不多不少正好等于组合数的数值 C(n, m)!
• 二叉树的总节点数与叶子数同阶。因此该递归函数的时间复杂度严格为 O(C(n, m))(对应选项 C)!
5.5 带函数调用栈的 C++ 单步代码跟踪实验室
借助下方交互式追踪器,体验函数递归调用时调用栈的压栈(Push)与出栈(Pop)以及变量值的实时变化过程:
互动实验 04
递归求阶乘 fact(3) 调用栈与变量追踪器
课后强化测验
模块五 · 全真过关检测(共5题)
分析以下 C++ 核心代码段的时间复杂度(以大 O 记号表示):
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j *= 2) {
sum += a[i];
}
}
【解题精析】
外层循环执行 n 次,内层循环 j 每次倍增执行 log₂ n 次。总计算次数为 n · log₂ n,即 O(n log n)。故选 B。
外层循环执行 n 次,内层循环 j 每次倍增执行 log₂ n 次。总计算次数为 n · log₂ n,即 O(n log n)。故选 B。
阅读以下计算组合数 C(n, m) 的递归函数,其时间复杂度为( )。
int C(int n, int m) {
if (m == 0 || m == n) return 1;
return C(n - 1, m) + C(n - 1, m - 1);
}
【解题精析】
每个到达的递归基叶子都返回 1,最终累加的值就是 C(n, m)。整棵树叶子节点总数严格等于 C(n, m),总节点规模与之同阶,故时间复杂度为 O(C(n, m))。故选 C。
每个到达的递归基叶子都返回 1,最终累加的值就是 C(n, m)。整棵树叶子节点总数严格等于 C(n, m),总节点规模与之同阶,故时间复杂度为 O(C(n, m))。故选 C。
阅读以下程序片段,输出结果为( )。
int s = 0, i = 1;
while (i <= 5) {
if (i % 2 == 1) s += i * 2;
else s += i;
i++;
}
cout << s << endl;
【解题精析】
跟踪累加:i=1(s=2) → i=2(s=4) → i=3(s=10) → i=4(s=14) → i=5(s=24)。最终输出 24。故选 C。
跟踪累加:i=1(s=2) → i=2(s=4) → i=3(s=10) → i=4(s=14) → i=5(s=24)。最终输出 24。故选 C。
若输入两个不同的正整数 x 和 y,阅读以下函数:
int calc(int x, int y) {
x = x ^ y;
y = x ^ y;
x = x ^ y;
return x;
}
该函数最终返回的结果是( )。
【解题精析】
异或三步交换值:第二步 y 变为原 x,第三步 x 变为原 y,最终返回 x 即返回了原始的 y。故选 B。
异或三步交换值:第二步 y 变为原 x,第三步 x 变为原 y,最终返回 x 即返回了原始的 y。故选 B。
阅读以下二分查找的递归实现代码,当在大小为 n 的有序数组中进行查找时,该程序占用的最大调用栈空间复杂度为( )。
int bsearch(int a[], int l, int r, int target) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (a[mid] > target) return bsearch(a, l, mid - 1, target);
return bsearch(a, mid + 1, r, target);
}
【解题精析】
每次二分区间折半(n → n/2 → n/4 → ... → 1),调用栈深度至多为 log₂ n + 1 层,因此其递归栈空间复杂度为 O(log n)。故选 B。
每次二分区间折半(n → n/2 → n/4 → ... → 1),调用栈深度至多为 log₂ n + 1 层,因此其递归栈空间复杂度为 O(log n)。故选 B。