题目

下列程序段的时间复杂度是（ ）。

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

错因

A

只看了外层 for (k = 1; k <= n; k *= 2) —— k 翻倍递增，循环 次，于是答 。但里面还嵌着一层完整的 次循环，单看外层等于完全忽略了嵌套乘法。

B

只看了内层 for (j = 1; j <= n; j++) —— 次，于是答 。漏了内层会被外层"乘上" 次这一事实。嵌套循环复杂度是内外层次数相乘，不是只取其一。

D

把外层也当成了 次（误读 k *= 2 为 k++），于是 。关键差别：k *= 2 让 k 走 1, 2, 4, 8, …, n 这条指数增长路径，达到 n 只需 步；而 k++ 才是线性 步。

总解析

两层循环各算各，再相乘。

外层 for (k = 1; k <= n; k *= 2)：

k 取值序列是 ，最大 ，所以 。

外层执行次数 。

内层 for (j = 1; j <= n; j++)：

每次执行恰好 次，与外层 k 无关。

总操作数：

类似题型对比：

• for (k=1; k<=n; k++) for (j=1; j<=n; j++) → （双线性）
• for (k=1; k<=n; k*=2) for (j=1; j<=n; j++) → （外指数 + 内线性，本题）
• for (k=1; k<=n; k*=2) for (j=1; j<=k; j++) → （内层和是几何级数 ≈ ）
  注意：内层上界变成 k 时，结果会差一个量级。

最终答案是 C（O(nlog₂n)）。