题目

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

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

错因

A

只数了外层循环的次数。外层 i 按 1, 2, 4, …, 倍增，确实只跑约 轮，但忽略了内层 j 在每一轮里要跑 i 次——内层不是常数操作。把外层的迭代次数当成总操作数，就会得到 。

C

把"双层循环 = 外层次数 × 内层次数"机械套用了。看到外层是 、内层最大跑到 ，就直接相乘得 。这种估法忽略了内层 i 的值随外层每次翻倍，绝大多数轮次内层只跑很少次（1, 2, 4, …），不能用最后一轮的次数代表所有轮次。

D

把所有双重循环都默认成 ，没看清外层是 i *= 2 而不是 i++。如果外层是线性的、内层也是线性的才会到 ；这里外层是对数级的，整体远小于 。

总解析

思路：双重循环的总操作数 = 内层执行次数对外层各轮求和。

外层变量 i 取值依次是 （其中 ，约 轮）。每一轮内层执行 i 次。

总执行次数：

这是一个等比数列求和，公比为 2，最后一项的值大约就是 ，整个和也是 量级——而不是 。

最终答案是 B（）。