模块 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. 归零律: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
11奇数+ 1 × 2 = 22
22偶数+ 24
33奇数+ 3 × 2 = 610
44偶数+ 414
55奇数+ 5 × 2 = 1024

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: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)。

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;
• 中间所有非叶子节点,仅仅做了一件事:把左子树和右子树返回的数字相加(return C(...) + C(...));
• 换句话说,最终函数返回的庞大组合数数值 C(n, m),全都是由所有的递归基叶子节点“+ 1”累加而成的!
• 这意味着:整棵递归树的叶子节点个数,恰好不多不少正好等于组合数的数值 C(n, m)!
• 二叉树的总节点数与叶子数同阶。因此该递归函数的时间复杂度严格为 O(C(n, m))(对应选项 C)!

5.5 带函数调用栈的 C++ 单步代码跟踪实验室

借助下方交互式追踪器,体验函数递归调用时调用栈的压栈(Push)与出栈(Pop)以及变量值的实时变化过程:

互动实验 04

递归求阶乘 fact(3) 调用栈与变量追踪器

课后强化测验

模块五 · 全真过关检测(共5题)

第 1 题 2025海淀第二赛段真题第19题 4 分
分析以下 C++ 核心代码段的时间复杂度(以大 O 记号表示):
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j *= 2) {
        sum += a[i];
    }
}
A. O(n)
B. O(n log n)
C. O(n log(log n))
D. O(n²)
【解题精析】
外层循环执行 n 次,内层循环 j 每次倍增执行 log₂ n 次。总计算次数为 n · log₂ n,即 O(n log n)。故选 B。
第 2 题 2025海淀第二赛段真题第20题 4 分
阅读以下计算组合数 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);
}
A. O(2ⁿ)
B. O(2ᵐ · (n - m))
C. O(C(n, m))
D. O(m · (n - m))
【解题精析】
每个到达的递归基叶子都返回 1,最终累加的值就是 C(n, m)。整棵树叶子节点总数严格等于 C(n, m),总节点规模与之同阶,故时间复杂度为 O(C(n, m))。故选 C。
第 3 题 2025海淀第二赛段真题第16题衍生 4 分
阅读以下程序片段,输出结果为( )。
int s = 0, i = 1;
while (i <= 5) {
    if (i % 2 == 1) s += i * 2;
    else s += i;
    i++;
}
cout << s << endl;
A. 15
B. 20
C. 24
D. 25
【解题精析】
跟踪累加:i=1(s=2) → i=2(s=4) → i=3(s=10) → i=4(s=14) → i=5(s=24)。最终输出 24。故选 C。
第 4 题 2025海淀第二赛段真题第17题 4 分
若输入两个不同的正整数 x 和 y,阅读以下函数:
int calc(int x, int y) {
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    return x;
}
该函数最终返回的结果是( )。
A. 原始的 x
B. 原始的 y
C. x ⊕ y
D. 0
【解题精析】
异或三步交换值:第二步 y 变为原 x,第三步 x 变为原 y,最终返回 x 即返回了原始的 y。故选 B。
第 5 题 递归调用栈深度分析 4 分
阅读以下二分查找的递归实现代码,当在大小为 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);
}
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
【解题精析】
每次二分区间折半(n → n/2 → n/4 → ... → 1),调用栈深度至多为 log₂ n + 1 层,因此其递归栈空间复杂度为 O(log n)。故选 B。

🎉 恭喜学完全部五大知识模块!

已掌握海淀第二赛段全部核心算法与离散思维。现在,检验你的终极时刻到了!

教研文档 进入 120 分钟全真模考 →