CSP-S 2022 第一轮 第13题：对于给定的n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（）。

题目

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

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

选项

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n\sqrt{n})$
• D. $O(n^2)$

答案

B

题解

答案是 B．\(O(n\log n)\)。

分别看两层循环：

• 外层循环：i 从 \(0\) 到 \(n-1\)，共执行 \(n\) 次。
• 内层循环：j 每次乘以 \(2\)，依次为 \(1,2,4,8,\ldots\)。经过 \(t\) 次后，\(j=2^t\)，达到 \(n\) 时停止，因此执行次数约为 \(\log_2 n\)。
• 循环体：k = k + n / 2 只是一次除法和一次加法，耗时为 \(O(1)\)，并不是执行 \(n/2\) 次。

所以总时间复杂度为： \[ O(n\times\log_2 n)=\boxed{O(n\log n)}. \]

记忆方法：循环变量每次加 \(1\)，通常是线性次数；每次乘 \(2\)，通常是对数次数。