CSP-S 提高级 · CSP 2022 提高级第一轮 第 13 题

对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 1; j < n; j*=2) {
        k = k + n / 2;
    }
}

别被两层循环吓住，核心就盯住内层那个 j 的变化：每次乘 2 意味着循环次数是对数级的，再乘外层的 n 次，答案自然就出来了。

最大坑就是看到嵌套循环就条件反射选 O(n^2)，这是把 j++ 的经验套用到 j*=2 上了。还有种情况是误以为 j 从 1 乘到 n 要 n 次，其实只要乘到比 n 大就停了，次数远少于 n。

这道题考查的是时间复杂度分析，特别是循环结构中变量变化步长对复杂度的影响。命题人喜欢用这种「看似复杂实则简单」的嵌套循环来挖坑，就是看学生会不会机械地套用「两层循环就是 n 平方」的公式。拿到题先别急着套公式，得先拆解每一层循环到底跑多少次。外层循环 i 从 0 跑到 n-1，每次加 1，这很直观，就是 n 次。内层循环 j 从 1 开始，每次乘 2，直到 j 不小于 n 为止。这里的关键是理解「乘 2」意味着 j 的取值是 1, 2, 4, 8, 16, ...，这是一个等比数列。我们要找的是这个数列里有多少项小于 n。设循环跑了 t 次，那么最后一次 j 的值是 2^{t-1}，它必须小于 n，而下一次 2^t 就要大于等于 n。两边取对数，t 大约是 log₂n。也就是说，内层循环执行 log₂n 次。两层循环独立，总次数就是 n 乘以 log₂n，即 O(n log n)。这个推导过程必须写清楚，不能只给结论。学生最容易错的地方就是忽略 j 的变化方式，或者误以为 j 从 1 乘到 n 需要 n 次（其实只需要 log₂n 次）。另外，还要注意题目里 j 的初始值是 1，终止条件是 j < n，所以最后一次循环 j 会达到刚好大于等于 n 的值，循环结束，次数确实是 log₂n。考频方面，循环结构是基础中的基础，题库里一共考了 609 题，覆盖所有级别。从近年趋势看，2023 年突然考了 77 题，2024 年更是飙升到 128 题，2025 年达到 158 题，2026 年预测也有 161 题，说明这个知识点在近期考试中非常高频，尤其是 CSP 提高级和 GESP 高级别。这类题目在提高级中占比稳定，属于必考内容，学生必须熟练掌握。基于这个考频趋势，未来几年这类分析循环复杂度的题目大概率还会继续出现，而且可能会结合更复杂的嵌套或条件依赖来增加难度，比如内层循环的终止条件依赖外层变量，那就不能简单相乘了，需要求和。但就本题而言，内外层独立，直接相乘即可。所以正确答案是 B，O(n log n)。