为何这段嵌套循环的时间复杂度为O(n)而非O(nlogn)？

先看你给出的代码：

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

你的初始思路错在把每个内层循环的次数都近似成logn，但实际上**log_i n会随着i的增大快速减小**，不能直接用(n-2)*logn来估算总和。我们可以把外层循环的i分成两部分拆解求和：

1. 当i > √n时的情况 #

当i大于√n时，i² > n（因为i>√n → i*i >n）。内层循环里j从1开始，第一次迭代后j=i <n，第二次迭代j=i*i ≥n，循环直接终止。所以这部分每个i对应的内层循环只执行1次。

这部分i的数量是(n-1) - √n ≈n（当n足够大时，√n相对于n可以忽略），所以这部分的总操作次数是O(n)。

2. 当i ≤ √n时的情况 #

当i≤√n时，log_i n的最大值是log_2 n（因为i越小，log_i n越大），而这部分i的总数最多是√n个。所以这部分的总操作次数是√n * logn。

但当n趋向于无穷大时，√n * logn的增长速度远慢于n（比如n=10^{6时，√n=1000，log₂(n)≈20，乘积是20000，远小于10}6），所以这部分是O(n)的低阶项，在复杂度分析中可以忽略。

总和分析 #

把两部分加起来，总操作次数是O(n) + O(√n logn) = O(n)，这就是为什么老师说时间复杂度是O(n)，也是你运行时结果接近2n的原因——低阶项占比极小，主要贡献来自i>√n的部分。

内容的提问来源于stack exchange，提问作者David Izhaki