题目

以下 C 代码的时间复杂度是（ ）。

int count = 0;
for (int i=0; i*i<n; i++)
    for (int j=0; j<i; j++)
        count++;

错因

A

误以为外层循环条件 i*i<n 等价于"对数次循环"。i*i<n 等价于 ，外层共执行 次，是平方根级别而非对数级别——把"开方"和"取对数"混淆了。

C

把外层 次循环和内层"最多 "次循环又乘上一个 ，得到 的错误估计。这一步多出来的 没有任何来源——题中两层都是普通的递增循环，不存在二分或对数行为。

D

按"两层 for 循环 ≈ "的定式套出 。但本题外层只跑到 就结束，并非 次；只有当外层是 i<n 才会得到 。属于忽视循环上界、机械套模板的错误。

总解析

思路：内外层循环次数都依赖 ，需要把"内层执行次数"对外层求和。

外层循环：条件是 i*i<n，即 ，所以 取 ，共约 次。

内层循环：当外层为 时，内层 从 0 跑到 ，执行 次。

总执行次数：

去掉常数因子，时间复杂度为 。

最终答案是 B。